//降序
//#include<stdio.h>
//struct stu{
//    char name;
//    int age;
//};
//int cmp(const void*r1,const void*r2){
//    return *(int*)r2-*(int*)r1;
//}
//int cmpchar(const void*r1,const void*r2){
//    return *(char*)r2-*(char*)r1;
//}
//void swap(char*r1,char*r2,int width){
//    int i=0;
//    char temp=0;
//    for(i=0;i<width;i++){
//        temp=*r1;
//        *r1=*r2;
//        *r2=temp;
//        r1++;
//        r2++;
//    }
//}
//void bubble_sort(void*arr,int sz,int width,int(*cmp)(const void*r1,const void*r2)){
//    int i=0;
//    for(i=0;i<sz-1;i++){
//        int j=0;
//        for(j=0;j<sz-1-i;j++){
//            if(cmp((char*)arr+j*width,(char*)arr+(j+1)*width)>0){
//                swap((char*)arr+j*width,(char*)arr+(j+1)*width,width);
//            }
//        }
//    }
//}
//int main(){
//    int arr[]={3,5,4,2,6,7,22,77,11};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    int width=sizeof(arr[0]);
//    bubble_sort(arr,sz,width,cmp);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    printf("\n");
//    char arr1[]={'c','d','b','l'};
//    int sz1=sizeof(arr1)/sizeof(arr1[0]);
//    int width1=sizeof(arr1[0]);
//    bubble_sort(arr1,sz1,width1,cmpchar);
//    for(i=0;i<sz1;i++){
//        printf("%c ",arr1[i]);
//    }
//    return 0;
//}
//字母左旋:
//#include<stdio.h>
//#include <string.h>
//#include <assert.h>
//void left_move(char*arr,int len,int k){
//    int i=0;
//    assert(arr!=NULL);//不为空指针，非0，
//    for(i=0;i<k;i++){
//        int j=0;
//        char temp=*arr;//第一步，先挪走第一位，倘若第一步和第二步不分开（都放到循环中），会导致左旋的字符发生变化
//        for(j=0;j<len-1;j++){
//            *(arr+j)=*(arr+j+1);//第二步，把剩下的往前挪
//        }
//        *(arr+len-1)=temp;//三步分开，第三步，把第一位放到最后一位，倘若第二步和第三步不分开，会导致最后一位被多次赋值
//    }
//}
//int main(){
//    char arr[]={"abcdef"};
//    int len=strlen(arr);
//    int k=2;
//    left_move(arr,len,k);
//    printf("%s",arr);
//    return 0;
//}
//字母左旋，三步翻转法:
//#include<stdio.h>
//#include <string.h>
//#include <assert.h>
//void reverse(char*left,char*right){
//    assert(left!=0);
//    assert(right!=0);
//    char temp=0;
//    while(left<right){
//        temp=*left;
//        *left=*right;
//        *right=temp;
//        left++;
//        right--;//别忘了设置循环终止条件
//    }
//
//}
//void left_move(char*arr,int len,int k){
//    reverse(arr,arr+k-1);
//    reverse(arr+k,arr+len-1);
//    reverse(arr,arr+len-1);
//}
//int main(){
//    char arr[]={"abcdef"};
//    assert(arr);
//    int len=strlen(arr),k=2;
//    assert(k<=len);//左旋字符数不能超过总字符数
//    left_move(arr,len,k);
//    printf("%s",arr);
//    return 0;
//}
//给出两个数，求它们的最大公约数:
//#include<stdio.h>
//int main(){
//    int m=0,n=0,z=0;
//    scanf("%d%d",&m,&n);
//    while(z=m%n){
//        m=n;
//        n=z;
//    }
//    printf("%d",n);
//    return 0;
//}
//检查是否为左旋字符:
//#include<stdio.h>
//#include <string.h>
//void reverse(char*left,char*right){
//    while(left<right){
//        char temp=*left;
//        *left=*right;
//        *right=temp;
//        left++;
//        right--;
//    }
//}
//void left_move(char*arr1,int len,int i){
//    reverse(arr1,arr1+i-1);
//    reverse(arr1+i,arr1+len-1);
//    reverse(arr1,arr1+len-1);
//
//}
//int is_left_move(char*arr1,char*arr2,int len){
//    int i=0;
//    for(i=1;i<=len;i++) {
//        left_move(arr1,len,1);//如果i跟着变的话，第一次左旋一个字符，第二次要在已经左旋
//        // 了一个字符的基础上左旋两个字符，无法达到一个一个左旋的效果
//        if (strcmp(arr1,arr2)==0) {//字符数组要用strcmp，不能直接比较
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    char arr1[]={"abcdef"};//注意定义字符数组要有框
//    char arr2[]={"cdefab"};
//    int len=strlen(arr1);
//    int ret=is_left_move(arr1,arr2,len);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//复习求最大公约数:
//#include<stdio.h>
//int main(){
//    int m=4,n=2,r=0;
//    while(r=m%n){
//        m=n;
//        n=r;
//    }
//    printf("%d",n);
//    return 0;
//}
//#include<stdio.h>
//int gys(int m, int n){
//    if(m%n==0){
//        return n;
//    }
//    else{
//    return gys(n,m%n);}
//}
//int main(){
//    int m=2,n=4;
//    int n1=gys(m,n);
//    printf("%d",n1);
//    return 0;
//}
//#include<stdio.h>
//#include <string.h>
//void reverse(char*left,char*right){
//    char temp=0;
//    while(left<right){
//        temp=*left;
//        *left=*right;
//        *right=temp;
//        left++;
//        right--;
//    }
//}
//void left_move(char*arr1,int len,int k){
//    reverse(arr1,arr1+k-1);
//    reverse(arr1+k,arr1+len-1);
//    reverse(arr1,arr1+len-1);
//}
//int is_left_move(char*arr1,char*arr2,int len){
//    int i=0;
//    for(i=0;i<len;i++){
//        left_move(arr1,len,1);
//        if(strcmp(arr1,arr2)==0){
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    char arr1[]={"abcdef"};
//    char arr2[]={"cdefab"};
//    int len=strlen(arr1);
//    int ret=is_left_move(arr1,arr2,len);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//2、另一种方法检查arr2是否由arr1左旋得来
//#include<stdio.h>
//#include <string.h>
//
//int is_left_move(char*arr1,char*arr2){
//    int len1=strlen(arr1);
//    int len2=strlen(arr2);
//    if(len1!=len2){
//        return 0;
//    }
//    strncat(arr1,arr1,6);
//    int ret=strstr(arr1,arr2);//如果没有子串返回NULL
//    if(ret==NULL){
//        return 0;
//    }
//    else{
//        return 1;
//    }
//}
//int main(){
//    char arr1[]={"abcdef"};
//    char arr2[]={"cdefab"};
//    int ret=is_left_move(arr1,arr2);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//杨氏矩阵:矩阵的每行从左到右递增,每列从上到下递增,要在矩阵中查找某个数是否存在(也可以再尝试写出该数的行数和列数
//#include<stdio.h>
//int FindX(int arr[3][3],int k,int* l,int* r){
//    int x=0,y=*r-1;
//    while(x<=*l-1 && y>=0){
//        if(arr[x][y]>k){
//            y--;
//        }
//        else if(arr[x][y]<k){
//             x++;
//        }
//        else{
//            *l=x;
//            *r=y;//这步是求被查数的行列的
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    int arr[3][3]={{1,2,3},{4,5,6},{7,8,9}};
//    int k=7,l=3,r=3;
//    int ret=FindX(arr,k,&l,&r);
//    if(ret==1){
//        printf("Yes %d %d",l,r);
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//字母右旋,位数不定:
//#include<stdio.h>
//#include <string.h>
//#include <assert.h>
//
//void right_move(char*arr,int len,int k){
//    int i=0;
//    assert(arr!=NULL);
//    for(i=0;i<k;i++){
//        char temp=*(arr+len-1);
//        int j=0;
//        for(j=len-1;j>0;j--){//注意这里是右旋,所以从高到低应为--
//            *(arr+j)=*(arr+j-1);
//        }
//        *arr=temp;
//    }
//}
//int main(){
//    char arr[]={"abcdef"};
//    int len=strlen(arr);
//    int k=2;
//    right_move(arr,len,k);
//    printf("%s",arr);
//    return 0;
//}
//字母右旋，三步翻转法:
//#include<stdio.h>
//#include <string.h>
//#include <assert.h>
//void reverse(char*left,char*right){
//    assert(left!=0);
//    assert(right!=0);
//    char temp=0;
//    while(left<right){
//        temp=*left;
//        *left=*right;
//        *right=temp;
//        left++;
//        right--;
//    }
//}
//void right_move(char*arr,int len,int k){
//    assert(arr!=NULL);
//    reverse(arr+len-k,arr+len-1);//左边不是在右边的基础上增减,而是整体上看
//    reverse(arr,arr+len-k-1);
//    reverse(arr,arr+len-1);
//}
//int main(){
//    char arr[]={"abcdef"};
//    int len=strlen(arr);
//    int k=2;
//    right_move(arr,len,k);
//    printf("%s",arr);
//    return 0;
//}
//检查是否为右旋字符(普通方法:
//#include<stdio.h>
//#include <string.h>
//#include <assert.h>
//void right_move(char*arr1,int len1,int k){
//    char temp=0;
//    int i=0;
//    for(i=0;i<k;i++){
//        temp=*(arr1+len1-1);
//        int j=0;
//        for(j=len1-1;j>0;j--){//好好看看这个
//            *(arr1+j)=*(arr1+j-1);
//        }
//        *arr1=temp;
//    }
//}
//int is_right_move(char*arr1,char*arr2,int len1){
//    assert(arr1!=NULL);
//    assert(arr2!=NULL);
//    int i=0;
//    for(i=0;i<len1;i++){//注意这里最多右旋len次
//        right_move(arr1,len1,1);
//        if(strcmp(arr1,arr2)==0){//比较字符串不能直接比较,需要使用库函数
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    char arr1[]={"abcdef"};
//    char arr2[]={"efabcd"};
//    int len1=strlen(arr1);
//    int len2=strlen(arr2);
//    assert(arr1);
//    assert(arr2);
//    assert(len1==len2);
//    int ret=is_right_move(arr1,arr2,len1);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
////检查是否为右旋字符(普通方法:
//#include<stdio.h>
//#include <assert.h>
//#include <string.h>
//void right_move(char*arr1,int len1,int k){
//    char temp=0;
//    int i=0;
//    for(i=0;i<k;i++){
//        temp=*(arr1+len1-1);
//        int j=0;
//        for(j=len1-1;j>0;j--){//注意这里是递减
//            *(arr1+j)=*(arr1+j-1);
//        }
//        *arr1=temp;
//    }
//}
//int is_right_move(char*arr1,char*arr2,int len1){
//    assert(arr1);
//    assert(arr2);
//    int i=0;
//    for(i=0;i<len1;i++){
//        right_move(arr1,len1,1);
//        if(strcmp(arr1,arr2)==0){//别忘了字符串比较只能用strcmp函数
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    char arr1[]={"abcdef"};
//    char arr2[]={"efabcd"};
//    int len1=strlen(arr1);
//    int len2=strlen(arr2);
//    assert(len1==len2);
//    int ret=is_right_move(arr1,arr2,len1);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
////检查是否为右旋字符(普通方法(再来一遍:
//#include<stdio.h>
//#include <assert.h>
//#include <string.h>
//void right_move(char*arr1,int len1,int k){
//    int i=0;
//    char temp=0;
//    for(i=0;i<k;i++){
//        temp=*(arr1+len1-1);
//        int j=0;
//        for(j=len1-1;j>0;j--){
//            *(arr1+j)=*(arr1+j-1);
//        }
//        *arr1=temp;
//    }
//}
//int is_right_move(char*arr1,char*arr2,int len1){
//    assert(arr1);
//    assert(arr2);
//    int i=0;
//    for(i=0;i<len1;i++){
//        right_move(arr1,len1,1);
//        if(strcmp(arr1,arr2)==0){
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    char arr1[]={"abcdef"};
//    char arr2[]={"efabcd"};
//    int len1=strlen(arr1);
//    int len2=strlen(arr2);
//    assert(len1==len2);
//    int ret=is_right_move(arr1,arr2,len1);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//检查左旋
//#include<stdio.h>
//#include <string.h>
//#include <assert.h>
//void left_move(char*arr1,int len1,int k){
//    int i=0;
//    char temp=0;
//    for(i=0;i<k;i++){
//        temp=*arr1;
//        int j=0;
//        for(j=0;j<len1;j++){
//            *(arr1+j)=*(arr1+j+1);
//        }
//        *(arr1+len1-1)=temp;
//    }
//}
//int is_left_move(char*arr1,char*arr2,int len1){
//    assert(arr1);
//    assert(arr2);
//    int i=0;
//    for(i=0;i<len1;i++){
//        left_move(arr1,len1,1);
//        if(strcmp(arr1,arr2)==0){
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    char arr1[]="abcdef";
//    char arr2[]="cdefab";
//    int len1=strlen(arr1);
//    int len2=strlen(arr2);
//    assert(len1==len2);
//    int ret=is_left_move(arr1,arr2,len1);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
////检查右旋,方法二:
//#include<stdio.h>
//#include <string.h>
//#include <assert.h>
//void reverse(char*left,char*right){
//    while(left<right){
//        char temp=*right;
//        *right=*left;
//        *left=temp;
//        left++;
//        right--;
//    }
//}
//void right_move(char*arr1,int len1,int k){
//    reverse(arr1+len1-1-k,arr1+len1-1);//想左旋就先反转左边的,右旋就先反转右边的
//    reverse(arr1,arr1+len1-k-2);
//    reverse(arr1,arr1+len1-1);
//}
//int is_right_move(char*arr1,char*arr2,int len1){
//    assert(arr1);
//    assert(arr2);
//    int i=0;
//    for(i=0;i<len1;i++){
//        right_move(arr1,len1,1);
//        if(strcmp(arr1,arr2)==0){
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    char arr1[]="abcdef";
//    char arr2[]="efabcd";
//    int len1=strlen(arr1);
//    int len2=strlen(arr2);
//    assert(len1==len2);
//    int ret=is_right_move(arr1,arr2,len1);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
////检查右旋,方法三(检查所有左旋右旋:
//#include<stdio.h>
//#include <string.h>
//#include <assert.h>
//int is_right_move(char*arr1,char*arr2,int len1){
//    assert(arr1);
//    assert(arr2);
//    strncat(arr1,arr1,6);
//    int ret=strstr(arr1,arr2);
//    if(ret==NULL){
//        return 0;
//    }
//    else{
//        return 1;
//    }
//}
//int main(){
//    char arr1[]="abcdef";
//    char arr2[]="efabcd";
//    int len1=strlen(arr1);
//    int len2=strlen(arr2);
//    assert(len1==len2);
//    int ret=is_right_move(arr1,arr2,len1);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//复习求最大公约数:
//#include<stdio.h>
//int gys(int a,int b){
//    if(a%b==0){
//        return b;
//    }else{
//        return gys(b,a%b);
//    }
//}
//int main(){
//    int a=2,b=4;
//    printf("%d",gys(a,b));
//    return 0;
//}
//复习求最大公约数1:
//#include<stdio.h>
//int gys(int m,int n){
//    if(m%n==0){
//        return n;
//    }
//    else{
//        return gys(n,m%n);
//    }
//}
//int main(){
//    int m=2,n=4;
//    printf("%d",gys(m,n));
//    return 0;
//}
//复习求最大公约数2:
//#include<stdio.h>
//int main(){
//    int a=2,b=4,c=0;
//    while(c=a%b){
//        a=b;
//        b=c;
//    }
//    printf("%d",b);
//    return 0;
//}
//杨氏矩阵:矩阵的每行从左到右递增,每列从上到下递增,要在矩阵中查找某个数是否存在(也可以再尝试写出该数的行数和列数
//#include<stdio.h>
//int FindX(int arr[3][3],int k,int row,int col){
//    int i=0;
//    for(;i<row;i++){
//        if(arr[i][0]==k){
//            return 1;
//        }
//        else if(arr[i][1]==k){
//            return 1;
//        }
//        else if(arr[i][2]==k){
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    int arr[3][3]={{1,2,3},{3,4,5},{5,6,7}};
//    int k=5;
//    int ret=FindX(arr,k,3,3);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//杨氏矩阵:矩阵的每行从左到右递增,每列从上到下递增,要在矩阵中查找某个数是否存在(也可以再尝试写出该数的行数和列数
//#include<stdio.h>
//int FindX(int arr[3][3],int k,int row,int col){
//    int i=0;
//    for(i=0;i<row;i++){
//        int j=0;
//        for(j=0;j<col;j++){
//            if(arr[i][j]==k){
//                return 1;
//            }
//        }
//    }
//    return 0;
//}
//int main(){
//    int arr[3][3]={{1,2,3},{3,4,5},{5,6,7}};
//    int k=5;
//    int ret=FindX(arr,k,3,3);
//    if(ret==1){
//        printf("Yes");
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//杨氏矩阵:矩阵的每行从左到右递增,每列从上到下递增,要在矩阵中查找某个数是否存在
//#include<stdio.h>
//int FindX(int arr[3][3],int k,int* lx,int* ly){
//    int x=0,y=*ly-1;
//    while(x<=*lx-1&&y>=0){
//        if(arr[x][y]>k){
//            y--;
//        }
//        else if(arr[x][y]<k){
//            x++;
//        }
//        else{
//            *lx=x;
//            *ly=y;
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    int arr[3][3]={{1,2,3},{4,5,6},{7,8,9}};
//    int k=5,lx=3,ly=3;
//    int ret=FindX(arr,k,&lx,&ly);
//    if(ret==1){
//        printf("Yes\n");
//        printf("%d %d",lx,ly);
//    }
//    else{
//        printf("No");
//    }
//    return 0;
//}
//复习求最大公约数:
//#include<stdio.h>
//int main(){
//    int m=2,n=4,r=0;
//    while(r=m%n){
//        m=n;
//        n=r;
//    }
//    printf("%d",n);
//    return 0;
//}
//复习求最大公约数2:
//#include<stdio.h>
//int gys(int a,int b){
//    if(a%b!=0){
//        return gys(b,a%b);
//    }
//    return b;
//}
//int main(){
//    int a=2,b=4;
//    printf("%d",gys(a,b));
//    return 0;
//}
////1、实现strlen函数
//#include<stdio.h>
//#include <assert.h>
//int my_strlen(const char*arr){
//    int count=0;
//    assert(arr!=NULL);
//    while(*arr!=0){//因为这里的0代表的是ascii值为0，也就是NULL和'\0'，而字符串里的字符0ASCII值为48，所以不算
//        count++;
//        arr++;
//    }
//    return count;
//}
//int main(){
//    char arr[]={"qwer0"};
//    int ret=my_strlen(arr);
//    printf("%d",ret);
//    return 0;
//}
////实现strlen函数且不创建临时变量
//#include<stdio.h>
//int strlenn(char*arr){
//    if (*arr!='\0'){
//        return strlenn(arr+1)+1;
//    }
//    return 0;
//}
//int main(){
//    char arr[]={"abcdef"};
//    printf("%d",strlenn(arr));
//    return 0;
//}
//strcmp的实现
//#include<stdio.h>
//#include <assert.h>
//void mystrcmp(char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    while(*arr1++=*arr2++){};
//    *arr1=*arr2;
//}
//int main(){
//    char arr1[]={"abcdef"};
//    char arr2[]={"zhang"};
//    mystrcmp(arr1,arr2);
//    printf("%s",arr1);
//    return 0;
//}
//视频解法:
//#include<stdio.h>
//#include <assert.h>
//char* mystrcmp(char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    char*ret=arr1;
//    while(*arr1++=*arr2++){}
//    return ret;
//}
//int main(){
//    char arr1[]={"abcdef"};
//    char arr2[]={"zhang"};
//    printf("%s",mystrcmp(arr1,arr2));
//    return 0;
//}
//strcat函数实现(乱改过了
//#include<stdio.h>
//#include <assert.h>
//void mystrcat(char*arr1,char*arr2){
//    assert(arr1);
//    assert(arr2);
//    while(*arr1!='\0'){
//        arr1++;
//    }
//    while(*arr1=='\0'){
//        *arr1=*arr2;
////        arr2+=1;     不要加这条
//    }
//    while(*arr1!='\0'){
//        *arr1++=*(arr2)++;
//    }
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"yang"};
//    mystrcat(arr1,arr1);
//    printf("%s",arr1);
//    return 0;
//}
//#include<stdio.h>
//#include <assert.h>
//int main(){
//    int a=1;
//    assert(a!=1);
//    return 0;
//}
//strcat函数实现
//#include<stdio.h>
//#include <assert.h>
//char* strcatt(char*arr1,char*arr2){
//    assert(arr1);
//    assert(arr2);
//    char*ret=arr1;
//    while(*arr1!='\0'){
//        arr1++;
//    }
//    while(*arr1++=*arr2++){}
//    return ret;
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"yang"};
//    strcatt(arr1,arr2);
//    printf("%s",arr1);
//    return 0;
//}
//strcat的实现方法(自写版:
//#include<stdio.h>
//void strcatt(char*arr1,char*arr2){    //没加const，减分
//    while(*arr1!='\0'){               //没确认数组有效性，减分
//        arr1++;
//    }
//    while(*arr1=='\0'){
//        *arr1=*arr2;
//    }
//    while(*arr1++=*arr2++){;}
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"yang"};
//    strcatt(arr1,arr2);
//    printf("%s",arr1);
//    return 0;
//}
//strcat的实现方法(视频版:
//#include<stdio.h>
//#include <assert.h>
//char* strcatt(char*arr1,const char*arr2){ //没加const，减分
//    assert(arr1);
//    assert(arr2);
//    char* ret=arr1;
//    while(*arr1!='\0'){
//        arr1++;
//    }
//    while(*arr1++=*arr2++){;}
//    return ret;
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"yang"};
//    printf("%s",strcatt(arr1,arr2));
//    return 0;
//}
//strcat的实现方法(自写版:
//#include<stdio.h>
//#include <assert.h>
//void strcatt(char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    while(*arr1!='\0'){
//        arr1++;
//    }
//    while(*arr1++=*arr2++){;}
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"yang"};
//    strcatt(arr1,arr2);
//    printf("%s",arr1);
//    return 0;
//}
//strncat的实现方法(自写版:
//#include<stdio.h>
//#include <assert.h>
//void strncatt(char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    while(*arr1!='\0'){
//        arr1++;
//    }
//    while(*arr1=='\0'){
//        *arr1=*arr2;
//    }
//    while(*arr1++=*arr2++){;}
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"zhang"};
//    strncatt(arr1,arr2);
//    printf("%s",arr1);
//    return 0;
//}
//strcpy的实现:
//#include<stdio.h>
//#include <assert.h>
//void strcpyy(char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    while(arr1!=arr2){
//        *arr1=*arr2;
//        arr1++;
//        arr2++;
//    }
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"younger"};
//    strcpyy(arr1,arr2);
//    printf("%s",arr1);
//    return 0;
//}
//strcpy的实现:
//#include<stdio.h>
//#include <assert.h>
//
//char* strcpyy(char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    char*ret=arr1;
//    while(*arr1++=*arr2++){;}
//    return ret;
//}
//int main(){
//    char arr1[]={"a"};
//    char arr2[]={"younger"};
//    char*ret=strcpyy(arr1,arr2);
//    printf("%s",ret);
//    return 0;
//}
//#include<stdio.h>
//#include <assert.h>
//char* mystrcpy(char*arr1,const char*arr2){
//    assert(arr1!=NULL&&arr2!=NULL);  //也可以assert(arr1&&arr2)
//    char*ret=arr1;
//    while(*arr1++=*arr2++){}
//    return ret;
//}
//int main(){
//    char arr1[]={"abcdef"};
//    char arr2[]={"zhanggggg"};
//    char*ret=mystrcpy(arr1,arr2);
//    printf("%s",ret);
//    return 0;
//}
////strcmp的实现
//#include<stdio.h>
//#include <assert.h>
//int strcmpp(const char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    while(*arr1==*arr2){//这是比较不是赋值，也就是说当双方都是\0的时候为真，也就是1
//        if(*arr1=='\0'){
//            return 0;
//        }
//        arr1++;
//        arr2++;
//    };
//    if(*arr1>*arr2){//要注意直接拿arr的话，比较的不是【字符】的大小
//        return 1;
//    }
//    else{
//        return -1;
//    }
//}
//int main(){
//    char arr1[]={"ahang"};
//    char arr2[]={"bhang"};
//    int ret=strcmpp(arr1,arr2);
//    printf("%d",ret);
//    return 0;
//}
////strcmp的实现(返回数值不同版
//#include<stdio.h>
//#include <assert.h>
//int strcmpp(const char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    while(*arr1==*arr2){
//        if(*arr1=='\0'){
//            return 0;
//        }
//        arr1++;
//        arr2++;
//    }
//    return *arr1-*arr2;
//}
//int main(){
//    char arr1[]={"ahang"};
//    char arr2[]={"zng"};
//    int ret=strcmpp(arr1,arr2);
//    printf("%d",ret);
//    return 0;
//}
////strncat实现:
//#include<stdio.h>
//#include <assert.h>
//char* strncatt(char*arr1,const char*arr2,int n){
//    assert(arr1);
//    assert(arr2);
//    char*ret=arr1;//指向要返回的地址
//    while(*arr1!='\0'){//把arr1加到'\0'这个位置
//        arr1++;
//    }
//    while(n&&(*arr1++=*arr2++)!='\0'){//完成赋值，直到两个字符数组元素都为0时或者n为0时结束
//        n--;
//    }
//    *arr1='\0';//因为上一步在arr2等于'\0'时就停止了，还没有给arr1赋值'\0'
//    return ret;//指针存的地址
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"zhang"};
//    printf("%s",strncatt(arr1,arr2,6));
//    return 0;
//}
//strcpy:
//#include<stdio.h>
//#include <assert.h>
//char* strcpyy(char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    char*ret=arr1;
//    while((*arr1++=*arr2++)!='\0'){}
//    return ret;
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"yangggggg"};
//    printf("%s",strcpyy(arr1,arr2));
//    return 0;
//}
////strncpy:
//#include<stdio.h>
//#include <assert.h>
//char* strncpyy(char*arr1,const char*arr2,int k){
//    assert(arr1);
//    assert(arr2);
//    char*ret=arr1;
//    while(k&&(*arr1++=*arr2++)!='\0'){
//        k--;
//    }
//    *arr1='\0';
//    return ret;
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"younger"};
//    printf("%s",strncpyy(arr1,arr2,4));
//    return 0;
//}
//strncmp（自写:
//#include<stdio.h>
//#include <assert.h>
//int strncmpp(const char*arr1,const char*arr2,int k){
//    assert(arr1);
//    assert(arr2);
//    while(k&&*arr1==*arr2){
//        k--;//注意这里别忘了设置好循环终止条件
//        if(k==0||*arr1=='\0'){
//            return 0;
//        }
//        arr1++;
//        arr2++;
//    }
//    return *arr1-*arr2;
//
//}
//int main(){
//    const char arr1[]={"zhang"};
//    const char arr2[]={"zhanz"};
//    printf("%d",strncmpp(arr1,arr2,5));
//    return 0;
//}
//strncmp的不同写法:
//#include<stdio.h>
//#include <assert.h>
//int strncmpp(char* arr1,char*arr2,int k){//忘了加const
//    assert(arr1);
//    assert(arr2);
//    while(k&&(*arr1==*arr2)){
//        k--;
//        if(*arr1=='\0'||k==0){
//            return 0;
//        }
//        arr1++;
//        arr2++;
//    }
//    return *arr1-*arr2;
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"zhana"};
//    printf("%d",strncmpp(arr1,arr2,3));
//    return 0;
//}
//#include<stdio.h>
//#include <assert.h>
//
//int strncmpp(char*arr1,char*arr2,int k){//忘了加const
//    assert(arr1);
//    assert(arr2);
//    while(k&&*arr1==*arr2){
//        k--;
//        if(k==0||*arr1=='\0'){
//            return 0;
//        }
//        arr1++;
//        arr2++;
//    }
//    return *arr1-*arr2;
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"zhanz"};
//    printf("%d",strncmpp(arr1,arr2,5));
//    return 0;
//}
////strncmp for循环做法:
//#include<stdio.h>
//#include <assert.h>
//int strncmpp(char*arr1,char*arr2,int k){//忘了加const
//    assert(arr1);
//    assert(arr2);
//    int i=0;
//    for(i=0;i<k;i++){
//        if(*(arr1+i)>*(arr2+i)){
//            return 1;
//        }
//        else if (*(arr1+i)<*(arr2+i)){
//            return -1;
//        }
//        else if(*(arr1+i)==0||*(arr2+i)==0){
//            break;//注意这里是break不是return0，当不是大于也不是小于的情况下，直接会到下一个i，不判断*arr1==*arr2，
//                  // 直到其中一个字符数组到'\0'时跳出循环，说明前面的都相等了，循环外面return 0就派上用场了
//        }
//    }
//    return 0;
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"zhanz"};
//    printf("%d",strncmpp(arr1,arr2,4));
//    return 0;
//}
////strncmp 最简单的写法？
//#include<stdio.h>
//#include <assert.h>
//int strncmpp(const char*arr1,const char*arr2,int k){
//    assert(arr1);
//    assert(arr2);
//    while(k--){
//        if(*arr1==0||*arr1!=*arr2){
//            return *arr1-*arr2;
//        }
//        arr1++;//给if创建循环条件
//        arr2++;
//    }
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"zhanz"};
//    printf("%d",strncmpp(arr1,arr2,5));
//    return 0;
//}
//////strcmp更简单版本
//#include<stdio.h>
//#include <assert.h>
//int strcmpp(const char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    while(*arr1&&*arr2&&*arr1==*arr2){
//        arr1++;
//        arr2++;
//    }
//    return *arr1-*arr2;
//}
//int main(){
//    char arr1[]={"zhang"};
//    char arr2[]={"zhanz"};
//    printf("%d",strcmpp(arr1,arr2));
//    return 0;
//}
//strstr实现:
//#include<stdio.h>
//#include <assert.h>
//char* strstrr(const char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    char* s1,*s2;
//    char* cur=(char*)arr1;
//    if(*arr2=='\0'){
//        return (char*)arr1;
//    }
//    while(*cur){
//        s1=cur;
//        s2=(char*)arr2;//这两步不能少,s1设定调整每次比对的母串起始位置，s2设定子串起始位置
//        while(*s1&&*s2&&(*s1==*s2)){//循环中设定了要用的变量就不能再使用外部变量进行操作
//            s1++;
//            s2++;
//        }
//        if(*s2=='\0'){
//            return cur;
//        }
//        cur++;//是++不是--，因为只有++才能让cur往后走，直到'\0'
//    }
//    return NULL;
//}
//int main(){
//    char arr1[]={"zhanggzhang"};
//    char arr2[]={"zhanggzhang"};
//    printf("%s",strstrr(arr1,arr2));
//    return 0;
//}
//#include<stdio.h>
//#include <assert.h>
//char*strstrr(const char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    char*s1,*s2;
//    char*cur=(char*)arr1;
//    if(!*arr2){
//        return (char*)arr1;
//    }
//    while(*cur){
//        s1=cur;
//        s2=(char*)arr2;
//        while(*s1&&*s2&&*s1==*s2){
//            s1++;
//            s2++;
//        }
//        if(!*s2){
//            return cur;
//        }
//        cur++;
//    }
//    return NULL;
//}
//int main(){
//    char arr1[]={"zhanggzhang"};
//    char arr2[]={"gz"};
//    printf("%s",strstrr(arr1,arr2));
//    return 0;
//}
//#include<stdio.h>
//#include<assert.h>
//char* strstrr(const char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    char*s1,*s2;
//    char*cur=(char*)arr1;
//    if(!*arr2){
//        return (char*)arr1;
//    }
//    while(*cur){
//        s1=cur;
//        s2=(char*)arr2;
//        while(*s1&&*s2&&*s1==*s2){
//            s1++;
//            s2++;
//        }
//        if(!*s2){
//            return cur;
//        }
//        cur++;
//    }
//}
//int main(){
//    char arr1[]={"zhanggzhang"};
//    char arr2[]={"gz"};
//    printf("%s",strstrr(arr1,arr2));
//    return 0;
//}
//strstr实现:
//#include<stdio.h>
//#include<assert.h>
//char* strstrr(const char*arr1,const char*arr2){
//    assert(arr1);
//    assert(arr2);
//    char*s1,*s2;
//    char*cur=(char*)arr1;
//    if(!*arr2){
//        return (char*)arr1;
//    }
//    while(*cur){
//        s1=cur;
//        s2=(char*)arr2;
//        while(*s1&&*s2&&*s1==*s2){
//            s1++;
//            s2++;
//        }
//        if(!*s2){
//            return cur;
//        }
//        cur++;
//    }
//    return NULL;
//}
//int main(){
//    char arr1[]={"zhanggyang"};
//    char arr2[]={"gy"};
//    printf("%s",strstrr(arr1,arr2));
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char a='a';
//    a=a-32;
//    printf("%c",a);
//    return 0;
//}
//memcpy:
//#include<stdio.h>
//#include<assert.h>
//struct s{
//    char name[20];
//    int age;
//};
//void* memcpyy(void*stu2,const void*stu1,size_t k){
//    assert(stu1);
//    assert(stu2);
//    void*ret=stu2;//要返回的值需要是原来的格式
//    while(k--){
//        *(char*)stu2=*(char*)stu1;
//        (char*)stu1++;
//        (char*)stu2++;
//    }
//    return ret;
//}
//int main(){
//    struct s stu1[]={{"younger",18},{"yang",21}};
//    struct s stu2[3]={0};
//    char*ret=memcpyy(stu2,stu1,sizeof(stu1));
//    printf("%d",stu2[0].age);
//    return 0;
//}
////memcpyy:
//#include<stdio.h>
//#include<assert.h>
//struct s{
//    char name[20];
//    int age;
//};
//void* memcpyy(void*stu2,const void*stu1,size_t k){
//    assert(stu1);
//    assert(stu2);
//    void* ret=(char*)stu2;
//    char*ret1=(char*)stu2;
//    char*ret2=(char*)stu1;
//    while(k--){
//        *ret1++=*ret2++;
//    }
//    return ret;
//}
//int main(){
//    struct s stu1[]={{"zhang",18},{"yang",21}};
//    struct s stu2[3]={0};
//    char* ret=memcpyy(stu2,stu1,sizeof(stu1));
//    printf("%s",ret);
//    return 0;
//}
//memcpyy:
//#include<stdio.h>
//#include<assert.h>
//struct s{
//    char name[20];
//    int age;
//};
//void* memcpyy(void*stu2,const void*stu1,size_t k){
//    assert(stu1);
//    assert(stu2);
//    char*ret=(char*)stu2;
//    char*ret1=(char*)stu1;
//    char*ret2=(char*)stu2;
//    while(k--){
//        *ret2++=*ret1++;
//    }
//    return ret;
//}
//int main(){
//    struct s stu1[]={{"zhang",18},{"younger",22}};
//    struct s stu2[3]={0};
//    char*ret = memcpyy(stu2,stu1,sizeof(stu1));
//    printf("%s",ret);
//    //printf("%s",stu2[0].name);
//    return 0;
//}
//memcpyy:
//#include<stdio.h>
//#include<assert.h>
//struct s{
//    char name[20];
//    int age;
//};
//void* memcpyy(void*stu2,const void*stu1,size_t k){
//    assert(stu1);
//    assert(stu2);
//    char*ret=(char*)stu2;
//    char*ret2=(char*)stu2;
//    char*ret1=(char*)stu1;
//    while(k--){
//        *ret2++=*ret1++;
//    }
//    return ret;
//}
//int main(){
//    struct s stu1[]={{"zhang",19},{"yang",22}};
//    struct s stu2[]={0};
//    char*ret=memcpyy(stu2,stu1,sizeof(stu1));
//    printf("%s",ret);
//    return 0;
//}
//memmove正确写法:
//#include<stdio.h>
//#include<assert.h>
//void* memmovee(const void*src,void*dest,size_t k){
//    assert(src);
//    assert(dest);
//    void*ret=dest;
//    char*srcc=(char*)src;
//    char*destt=(char*)dest;
//    if(srcc<destt&&srcc+k>destt){
//        while(k--){
//            *(destt+k)=*(srcc+k);
//            destt--;
//            srcc--;
//        }
//    }
//    else{
//        while(k--){
//            *destt=*srcc;
//            destt++;
//            srcc++;
//        }
//    }
//    return ret;
//}
//int main(){
//    int arr[]={1,2,3,4,5,6,7,8,9};
//    memmovee(arr,arr+2,8);
//    int i=0;
//    for(i=0;i<9;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
////每次只修改一个字节，所以对象要是可以只改一字节的内容，比如字符：
//#include<stdio.h>
//#include <string.h>
//int main(){
//    int arr[10]={0};
//    memset(arr,1,40);
//    int i=0;
//    for(i=0;i<10;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//memcpy:
//#include<stdio.h>
//#include<assert.h>
//struct s{
//    char name[20];
//    int age;
//};
//void* memcpyy(void*dest,const void*src,size_t k){
//    assert(dest);
//    assert(src);
//    void*ret=(char*)dest;
//    char*destt=(char*)dest;
//    char*srcc=(char*)src;
//    while(k--){
//        *destt++=*srcc++;
//    }
//    return ret;
//}
//int main(){
//    struct s stu1[]={{"zhang",22},{"younger",16}};
//    struct s stu2[10]={0};
//    char*ret=memcpyy(stu2,stu1,sizeof(stu1));
//    printf("%s",stu2[1].name);
//    return 0;
//}
//memmove实现:
//#include<stdio.h>
//#include<assert.h>
//void*memmovee(const void*src,void*dest,size_t k){
//    assert(src);
//    assert(dest);
//    void*ret=dest;
//    char*srcc=(char*)src;
//    char*destt=(char*)dest;
//    if(srcc<dest&&srcc+k>dest){
//        while(k--){
//            *(destt+k)=*(srcc+k);
//            destt--;
//            srcc--;
//        }
//    }
//    else{
//        while(k--){
//            *destt=*srcc;
//            destt++;
//            srcc++;
//        }
//    }
//    return ret;
//}
//int main(){
//    int arr[]={1,2,3,4,5};
//    memmovee(arr,arr+2,8);
//    int i=0;
//    for(i=0;i<5;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//求阶乘:
//#include<stdio.h>
//int fact(int a){
//    if(a<=1){
//        return 1;
//    }
//    else{
//        return a*fact(a-1);
//    }
//}
//int main(){
//    int a=3;
//    printf("%d",fact(a));
//    return 0;
//}
//冒泡排序:
//#include<stdio.h>
//#include <assert.h>
//void bubble_sort(int arr[],int sz){
//    assert(arr);
//    int i=0;
//    int temp=0;
//    for(i=0;i<sz-1;i++){
//        int j=0;
//        int flag=1;
//        for(j=0;j<sz-1-i;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j+1];
//                arr[j+1]=arr[j];
//                arr[j]=temp;
//                flag=0;
//            }
//            }
//        if(flag==1){
//            break;
//        }
//    }
//}
//int main(){
//    int arr[]={1,6,3,7,2};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    bubble_sort(arr,sz);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//再写一次冒泡排序,升序:
//#include<stdio.h>
//#include<assert.h>
//int bubble_sort(int arr[],int sz){
//    assert(arr);
//    int i=0;
//    int temp=0;
//    for(i=0;i<sz-1;i++){
//        int j=0;
//        int flag=0;
//        for(j=0;j<sz-1-i;j++){
//            if(arr[j+1]<arr[j]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=1;
//            }
//        }
//        if(flag==0){
//            break;
//        }
//    }
//}
//int main(){
//    int arr[]={1,3,2,5,4,7,6};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    bubble_sort(arr,sz);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//再写一次冒泡排序,降序:
//#include<stdio.h>
//#include<assert.h>
//void bubble_sort(int*arr,int sz){
//    assert(arr);
//    int i=0;
//    int flag=0;
//    for(i=0;i<sz-1;i++){
//        int j=0;
//        int temp=0;
//        for(j=0;j<sz-1-i;j++){
//            if(arr[j+1]>arr[j]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=1;
//            }
//        }
//        if(flag==0){
//            break;
//        }
//    }
//}
//int main(){
//    int arr[]={1,3,2,5,4,7,6};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    bubble_sort(arr,sz);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//递归求阶乘:
//#include<stdio.h>
//int fact(int a){
//    if(a<=1){
//        return 1;
//    }
//    else{
//        return a*fact(a-1);
//    }
//}
//int main(){
//    int a=3;
//    printf("%d",fact(a));
//    return 0;
//}
//求阶乘:
//#include<stdio.h>
//int fact(int a){
//    if(a<=1){
//        return 1;
//    }
//    else{
//        return a*fact(a-1);
//    }
//}
//int main(){
//    int a=3;
//    printf("%d",fact(a));
//    return 0;
//}      12行
//bubble_sort,升序,ascending order
//#include<stdio.h>
//#include<assert.h>
//void bubble_sort(int*arr,int sz){
//    assert(arr);
//    int i=0;
//    int flag=1;
//    for(i=0;i<sz-1;i++){
//        int j=0;
//        int temp=0;
//        for(j=0;j<sz-1-i;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=0;
//            }
//        }
//        if(flag){
//            break;
//        }
//    }
//}
//int main(){
//    int arr[]={1,3,2,5,4,7,6};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    bubble_sort(arr,sz);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//测试define
//enum color{
//    red,
//    green,
//    blue
//};
//#define red 3
//#define green 1
//#define blue 2
//#include<stdio.h>
//int main(){
//    enum color a=red;
//    printf("%d ",a);
//    return 0;
//}
//冒泡排序，升序
//#include<stdio.h>
//#include<assert.h>
//void bubble_sort(int*arr,int sz){
//    assert(arr);
//    int i=0,flag=1;
//    for(i=0;i<sz-1;i++){
//        int temp=0;
//        int j=0;
//        for(j=0;j<sz-1-i;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//            flag=0;
//            }
//        }
//        if(flag){
//            break;
//        }
//    }
//}
//int main(){
//    int arr[]={1,3,2,4,6,5,8,7};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    bubble_sort(arr,sz);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//冒泡排序，降序
//#include<stdio.h>
//#include<assert.h>
//void bubble_sort(int*arr,int sz){
//    assert(arr);
//    int i=0,flag=1;
//    for(i=0;i<sz-1;i++){
//        int j=0,temp=0;
//        for(j=0;j<sz-1-i;j++){
//            if(arr[j+1]>arr[j]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=0;
//            }
//        }
//        if(flag){
//            break;
//        }
//    }
//}
//int main(){
//    int arr[]={1,3,2,5,4,7,6,9,8};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    bubble_sort(arr,sz);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//冒泡排序，降序
//#include<stdio.h>
//#include<assert.h>
//void bubble_sort(int*arr,int sz){
//    assert(arr);
//    int i=0;
//    int flag=1;
//    for(i=0;i<sz-1;i++){
//        int j=0;
//        int temp=0;
//        for(j=0;j<sz-1-i;j++){
//            if(arr[j]<arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=0;
//            }
//        }
//        if(flag){
//            break;
//        }
//    }
//}
//int main(){
//    int arr[]={2,1,4,3,6,5,8,7,9};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    bubble_sort(arr,sz);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//万能排序,降序(部分:
//#include<stdio.h>
//#include<assert.h>
//int cmp(const void*r1,const void*r2){
//    return *(int*)r2-*(int*)r1;
//}
//int cmpp(const void*r1,const void*r2){
//    return *(char*)r2-*(char*)r1;
//}
//void swap(char*r1,char*r2,int width){
//    int i=0;
//    char temp=0;
//    for(i=0;i<width;i++){
//        temp=*r1;
//        *r1=*r2;
//        *r2=temp;
//        r1++;
//        r2++;
//    }
//
//}
//void bubble_sort(void*arr,int sz,int width,int (*cmp)(const void*r1,const void*r2)){
//    assert(arr);
//    int i=0;
//    for(i=0;i<sz-1;i++){//减一是因为会额外多排序一个
//        int j=0;
//        for(j=0;j<sz-i-1;j++){
//            if(cmp((char*)arr+j*width,(char*)arr+(j+1)*width)>0){
//                swap((char*)arr+j*width,(char*)arr+(j+1)*width,width);
//            }
//        }
//    }
//}
//int main(){
//    int arr1[]={2,1,4,3,6,5,8,7};
//    int sz1=sizeof(arr1)/sizeof(arr1[0]);
//    bubble_sort(arr1,sz1,sizeof(arr1[0]),cmp);
//    int i=0;
//    for(i=0;i<sz1;i++){//从0开始的
//        printf("%d ",arr1[i]);
//    }
//    printf("\n");
//
//    char arr2[]={'b','a','c'};
//    int sz2=sizeof(arr2)/sizeof(arr2[0]);
//    bubble_sort(arr2,sz2,sizeof(arr2[0]),cmpp);
//    int j=0;
//    for(j=0;j<sz2;j++){
//        printf("%c ",arr2[j]);
//    }
//    printf("\n");
//    return 0;
//}
//求阶乘:
//#include <stdio.h>
//int fac(int a){
//    if(a<=1){
//        return 1;
//    }
//    else{
//        return a*fac(a-1);
//    }
//}
//int main(){
//    int a=3;
//    int b=0;
//    b=fac(a);
//    printf("%d",b);
//    return 0;
//}
//#include<stdio.h>
//int fac(int a){
//    if(a<=1){
//        return 1;
//    }
//    else{
//        return a*fac(a-1);
//    }
//}
//int main(){
//    int a=3;
//    int b=fac(a);
//    printf("%d",b);
//    return 0;
//}
//字母左旋,两位:
//#include<stdio.h>
//#include <assert.h>
//#include <string.h>
//void reverse(int k,int len, char arr[]){
//    assert(arr);
//    int i=0;
//    for(i=0;i<k;i++){
//        char temp=*arr;
//        int j=0;
//        for(j=0;j<len-1;j++){
//            *(arr+j)=*(arr+j+1);
//        }
//        *(arr+len-1)=temp;
//    }
//    }
//int main(){
//    char arr[]={"abcdef"};
//    int k=2;
//    int len=strlen(arr);
//    reverse(k,len,arr);
//    printf("%s",arr);
//    return 0;
//}
//字母左旋,两位:
//#include<stdio.h>
//#include<string.h>
//#include<assert.h>
//void left_move(int k,int len,char*arr){
//    assert(arr);
//    int i=0;
//    for(i=0;i<k;i++){
//        int j=0;
//        char temp=*arr;
//        for(j=0;j<len-1;j++){
//            *(arr+j)=*(arr+j+1);
//        }
//        *(arr+len-1)=temp;
//    }
//}
//int main(){
//    char arr[]={"ABCDEF"};
//    int k=2;
//    int len=strlen(arr);
//    left_move(k,len,arr);
//    printf("%s",arr);
//    return 0;
//}
//求阶乘:
//#include<stdio.h>
//int fact(int a){
//    if(a>1){
//    int b=a;
//    return fact(a-1)*b;}
//    else{
//        return 1;
//    }
//}
//int main(){
//    int a=1;
//    printf("%d",fact(a));
//    return 0;
//}
//字母右旋两位:
//#include<stdio.h>
//#include<string.h>
//#include<assert.h>
//void right_move(int k,int len,char*arr){
//    assert(arr);
//    int i=0;
//    for(i=0;i<k;i++){
//        int j=0;
//        char temp=*(arr+len-1);
//        for(j=len-1;j>0;j--){
//            *(arr+j)=*(arr+j-1);
//        }
//        *arr=temp;
//    }
//}
//int main(){
//    char arr[]={"ABCDEF"};
//    int k=2;
//    int len=(int)strlen(arr);
//    right_move(k,len,arr);
//    printf("%s",arr);
//    return 0;
//}
//字母左旋两位:
//#include<stdio.h>
//#include<string.h>
//#include<assert.h>
//void left_move(int k,int len,char*arr){
//    assert(arr);
//    int i=0;
//    for(i=0;i<k;i++){
//        int j=0;
//        char temp=*arr;
//        for(j=0;j<len-1;j++){
//            *(arr+j)=*(arr+j+1);
//        }
//        *(arr+len-1)=temp;
//    }
//}
//int main(){
//    char arr[]={"ABCDEF"};
//    int k=2;
//    int len=(int)strlen(arr);
//    left_move(k,len,arr);
//    printf("%s",arr);
//    return 0;
//}
//右旋两位:
//#include<stdio.h>
//#include<string.h>
//#include<assert.h>
//void right_move(int k,int len,char*arr){
//    assert(arr);
//    int i=0;
//    for(i=0;i<k;i++){
//        int j=0;
//        char temp=*(arr+len-1);
//        for(j=len-1;j>0;j--){
//            *(arr+j)=*(arr+j-1);
//        }
//        *arr=temp;
//    }
//}
//int main(){
//    char arr[]={"ABCDEF"};
//    int k=2;
//    int len=(int)strlen(arr);
//    right_move(k,len,arr);
//    printf("%s",arr);
//    return 0;
//}
//冒泡排序，升序:
//#include<stdio.h>
//#include<assert.h>
//void bubble_sort(int sz,int*arr){
//    assert(arr);
//    int i=0;
//    int flag=0;
//    for(i=0;i<sz-1;i++){
//        int j=0;
//        int temp=0;
//        for(j=0;j<sz-1-i;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=0;
//            }
//            else{
//                flag=1;
//            }
//            }
//        if(flag){
//            break;
//        }
//    }
//}
//int main(){
//    int arr[]={1,3,2,4,6,5,8,7};
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    bubble_sort(sz,arr);
//    int i=0;
//    for(i=0;i<sz;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=4;
//    printf("%d*4",a);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int l=3;
//    int i=0;
//    for(i=0;i<l;i++){
//        int j=0;
//        for(j=0;j<l;j++){
//            int n=i;
//            while(i==j&&i!=0){
//                if(n--){
//                    printf(" ");
//                }
//                else{
//                    break;
//                }
//            }
//        }
//        printf("v");
//        int k=0;
//        for(k=l-1;k>=0;k--){
//            int m=2*k-1;
//            while(k+i==2&&m>0){
//                printf(" ");
//                m--;
//            }
//        }
//        if(i<l-1){
//            printf("v\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=0,b=0,c=0;
//    scanf("%d %d %d",&a,&b,&c);
//    while((a<=0||a>=100)||(b<=0||b>=100)||(c<=0||c>=100)){
//        printf("input error, please retype:\n");
//        scanf("%d %d %d",&a,&b,&c);
//    }
//    printf("score1=%d,score2=%d,score3=%d",a,b,c);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char a=0;
//    scanf("%c",&a);
//    printf("    %c\n   %c %c\n  %c %c %c\n %c %c %c %c\n%c %c %c %c %c",a,a,a,a,a,a,a,a,a,a,a,a,a,a,a);
//    return 0;
//}
//输入一个字符和一个数字，组成由该字符组成的该数字行数的金字塔（模型在桌面-暂存-文件里）:
//#include<stdio.h>
//int main(){
//    char a='1';
//    int n=5,n1=1;
//    scanf("%c %d",&a,&n);
//while(n--){
//    int an=1+(n1-1)*2;//这里必须放在循环内，以免其成为常量
//    int i=0;
//    for(i=n;i>0;i--){//是n不是n-1，因为n--已经将n-1了
//        printf(" ");
//    }
//    int j=0,k=-1;
//    for(j=1;j<=k+2;j++){
//        if(j%2==1){
//            printf("%c",a);
//        }
//        else{
//            printf(" ");
//        }
//        if(j==k+2&&j<an){//当j++到k+2时，这时候的需要++，这时候是一次循环的结束，也是另一次的开始
//            k+=2;
//        }
//    }
//    n1++;
//    printf("\n");
//}
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    printf("%c,%c,%c,%c,%c,%c,%c,%c,%c,%c,%c,%c",73, 32, 99, 97, 110, 32, 100, 111, 32, 105, 116 , 33);
//    return 0;
//}
//#include<stdio.h>
//int main() {
//    int c = 0, y = 0, m = 0, d = 0;
//    while (1) {
//        scanf("%d", &c);
//        y = c / 10000;
//        m = c / 100;
//        m = m % y;
//        d = c % 100;
//        if (y >= 1990 && y <= 2015 && m >= 1 && m <= 12 && d >= 1 && d <= 30) {
//            printf("year=%d\nmonth=%02d\ndate=%02d",y,m,d);
//            break;
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long a=0,b=0;
//    scanf("a=%ld,b=%ld",&a,&b);
//    if((a>=-2147483648&&a<=2147483647)&&(b>=-2147483648&&b<=2147483647)){
//        printf("a=%ld,b=%ld",b,a);
////        break;
//    }
//    else{
//        printf("超出范围！");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a = 40, c = 212;
//    printf("%d",(-8+22)*a-10+c/2);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n = 0;
//    while(1){
//        scanf("%d", &n);
//        if(n>=1000&&n<=9999){
//            int a = n / 1000;
//            int b = n % 1000;
//            b /= 100;
//            int c = n % 100;
//            c /= 10;
//            int d = n % 10;
//            int v = d*1000+c*100+b*10+a;
//            printf("%04d",v);
//            break;
//        }
//        else{
//            printf("不符合规则，请重新输入:");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    n=n%10;
//    printf("%d",n);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    float n=0;
//    scanf("%f",&n);
//    printf("%d",(int)n%10);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int x;
//    float a,b,c;
//    scanf("%d %f %f %f",&x,&a,&b,&c);
//    printf("The each subject score of  No. %d is %.2f,%.2f,%.2f",x,a,b,c);
//    return 0;
//}
//#include<stdio.h>
//#include<math.h>
//int main(){
//    int w=0,h=0;
//    float r=0;
//    scanf("%d %d",&w,&h);
//    r=w/pow(h/100.0,2);//隐式转换
//    printf("%.2f",r);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int w=0,h=0;
//    float r=0;
//    scanf("%d %d",&w,&h);
//    printf("%.2f",w/((h/100.0)*(h/100.0)));
//    return 0;
//}
//#include<stdio.h>
//#include<math.h>
//int main(){
//    int a=0,b=0,c=0;
//    scanf("%d %d %d",&a,&b,&c);
//    float cir=0,cir1=0,area=0;
//    cir=a+b+c;
//    cir1=1.0/2*cir;
//    area=sqrt(cir1*(cir1-a)*(cir1-b)*(cir1-c));
//    printf("circumference=%.2f area=%.2f",cir,area);
//    return 0;
//}
//#include<stdio.h>
//#include<math.h>
//int main(){
//    double pi=3.1415926,n=0;
//    scanf("%lf",&n);
//    double volume=0;
//    volume=4.0/3*pi*pow(n,3);
//    printf("%.3lf",volume);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char a=0,b=0;
//    scanf("%c\n%c",&a,&b);
////    a=a+32;
////    b=b+32;
//    printf("%c\n%c",a+32,b+32);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char n=0;
//    while((n=getchar())!='\n'){//确保不是换行符，也就是enter
//        if(n>='A'&&n<='Z'){
//            n=n+32;
//            printf("%c\n",n);
//            n=getchar();//开始读取第二个字符
//        }
//        else{
//            break;
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,h=0,m=0,m1=0;
////     while(1){
//    scanf("%d %d %d",&n,&h,&m);
//    if(m%h>0){
//        m1=n-m/h-1;
//        printf("%d",m1);
//    }else{
//        m1=n-m/h;
//        printf("%d",m1);
//    }
////                    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    printf("I lost my cellphone!");
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    printf("Name    Age    Gender\n");
//    printf("---------------------\n");
//    printf("Jack    18     man\n");
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=0,b=0,c=0,d=0,e=0;
//    float f=0;
//    scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
//    printf("%.1f",(a+b+c+d+e)/5.0);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=2;
//    printf("%d",a^2);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int ln=0,i=0;
//    for(i=10000;i<=99999;i++){
//        ln=(i/10000)*(i%10000)+(i/1000)*(i%1000)+(i/100)*(i%100)+(i/10)*(i%10);
//        if(ln==i){
//            printf("%d ",i);
//
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=0,b=0;
//    scanf("%d",&a);
//    getchar();
//    scanf("%d",&b);
//    return 0;
//}
//#include<stdio.h>
//#include<assert.h>
//void bubble_sort(int n,int arr[]){
//    assert(arr);
//    int i=0;
//    for(i=0;i<n-1;i++){
//        int j=0,temp=0,flag=1;
//        for(j=0;j<n-1-i;j++){
//            if(arr[j]<arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=0;
//            }
//        }
//        if(flag){
//            break;
//        }
//    }
//}
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    getchar();
//    int i=0,arr[50]={0};
//    for(i=0;i<n;i++){
//        scanf("%d ",&arr[i]);
//    }
//    bubble_sort(n,arr);
//    int j=0;
//    for(j=0;j<5;j++){
//        printf("%d ",arr[j]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char arr[30]={0};
//    int counta=0,countb=0,i=0;
//    scanf("%s",&arr);
//    int sz=sizeof(arr)/sizeof(arr[0]);
//    for(i=0;i<sz;i++){
//        if(arr[i]=='0'){
//            break;
//        }
//        else if(arr[i]=='B'){
//            countb++;
//        }
//        else if(arr[i]=='A'){
//            counta++;
//        }
//    }
//    if(counta==countb){
//        printf("E");
//    }
//    else if(counta>countb){
//        printf("A");
//    }
//    else{
//        printf("B");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        if(n>=140){
//            printf("Genius");
//        }
//        else{
//            break;
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        if(n>=90&&n<=100){
//            printf("Perfect");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        if(n>=60){
//            printf("Pass\n");
//        }
//        else{
//            printf("Fail\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0;
//    while(scanf("%ld",&n)!=EOF){
//        int m=n%2;
//        if(m==0){
//            printf("Even\n");
//        }
//        else{
//            printf("Odd\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=0,b=0,c=0;
//    scanf("%d %d %d",&a,&b,&c);
//    if(a>b&&a>c){
//        printf("%d",a);
//    }
//    else if(b>a&&b>c){
//        printf("%d",b);
//    }
//    else if(c>a&&c>b){
//        printf("%d",c);
//    }
//    return 0;
//}
//#include <stdio.h>
//int main ()
//{
//    int a,b,c;
//    scanf("%d %d %d",&a,&b,&c);
//    if(a>b){
//        if(b>c){
//            printf("%d",a);
//        }
//        else{
//            printf("%d",c);
//        }
//    }
//    else{
//        if(b<c){
//            printf("%d",c);
//        }
//        else{
//            printf("%d",b);
//        }
//    }
//}
//#include<stdio.h>
//int main(){
//    char n=0;
//    while(scanf("%c",&n)!=EOF){
//        getchar();
//        if(n=='A'||n=='a'||n=='E'||n=='e'||n=='I'||n=='i'||n=='O'||n=='o'||n=='U'||n=='u'){
//            printf("Vowel\n");
//        }
//        else{
//            printf("Consonant\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char n=0;
//    char arr[52]={'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
//    while(scanf("%c",&n)!=EOF){
//        getchar();
//        int i=0;
//        for(i=0;i<52;i++){
//            if(n==arr[i]){
//                printf("%c is an alphabet.\n",n);
//                i=60;
//            }
//        }
//        if(i==52){
//            printf("%c is not an alphabet.\n",n);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char n=0;
//    while(scanf("%c",&n)!=EOF){
//        getchar();
//        if(n>='A'&&n<='Z'){
//            printf("%c\n",n+32);
//        }
//        else if(n>='a'&&n<='z'){
//            printf("%c\n",n-32);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long a=0,b=0;
//    while(scanf("%ld %ld",&a,&b)!=EOF){
//        getchar();
//        if(a-b>0){
//            printf("%ld>%ld\n",a,b);
//        }
//        else if(a-b<0){
//            printf("%ld<%ld\n",a,b);
//        }
//        else{
//            printf("%ld=%ld\n",a,b);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int t=0;
//    while(scanf("%d",&t)!=EOF){
//        getchar();
//        if(t>0){
//            printf("1\n");
//        }
//        else if(t<0){
//            printf("0\n");
//        }
//        else{
//            printf("0.5\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=0,b=0,c=0;
//    while(scanf("%d %d %d",&a,&b,&c)!=EOF){
//        getchar();
//        if(a+b>c&&a+c>b&&b+c>a){
//            if(a==b&&b==c){
//                printf("Equilateral triangle!\n");
//            }
//            else if(a==b||a==c||b==c){
//                printf("Isosceles triangle!\n");
//            }
//            else{
//                printf("Ordinary triangle!\n");
//            }
//        }
//        else{
//            printf("Not a triangle!\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int w=0,h=0;
//    float hei=0,b=0;
//    while(scanf("%d %d",&w,&h)!=EOF){
//        getchar();
//        hei=h/100.0;
//        b=w/(hei*hei);
//        if(b<18.5){
//            printf("Underweight\n");
//        }
//        else if(b>=18.5&&b<=23.9){
//            printf("Normal\n");
//        }
//        else if(b>23.9&&b<=27.9){
//            printf("Overweight\n");
//        }
//        else{
//            printf("Obese\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//#include<math.h>
//int main(){
//    float a=0,b=0,c=0,delta=0;
//    while(scanf("%f %f %f",&a,&b,&c)!=EOF){
//        delta=b*b-4*a*c;
//        if(a==0){
//            printf("Not quadratic equation\n");
//        }
//        else{
//            if(delta==0){
//                printf("x1=x2=%.2f\n",-b/(2*a));
//            }
//            else if(delta>0){
//                float x1=0,x2=0;
//                x1=(-b+sqrt(delta))/(2*a);
//                x2=(-b-sqrt(delta))/(2*a);
//                printf("x1=%.2f;x2=%.2f\n",x2,x1);
//            }
//            else{
//                float x1=0,x2=0,shi=0,xu=0;
//                shi=-b/(2*a);
//                xu=sqrt(-delta)/(2*a);
//                printf("x1=%.2f-%.2fi;x2=%.2f+%.2fi",shi,xu,shi,xu);
//            }
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int year=0,month=0;
//    int montha[]={1,3,5,7,8,10,12};
//    int monthb[]={4,6,9,11};
//    while(scanf("%d %d",&year,&month)!=EOF){
//        getchar();
//        int i=0;
//        for(i=0;i<7;i++){
//            if(month==montha[i]){
//                printf("31\n");
//                break;
//            }
//        }
//        int j=0;
//        for(j=0;j<4;j++){
//            if(month==monthb[j]){
//                printf("30\n");
//                break;
//            }
//        }
//        if(month==2){
//            if((year%100!=0&&year%4==0)||year%400==0){
//                printf("29\n");
//            }
//            else{
//                printf("28\n");
//            }
//        }
//
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    double a=0,b=0;
//    char s=0;
//    scanf("%lf%c%lf",&a,&s,&b);
//    if(s!='+'&&s!='-'&&s!='*'&&s!='/'){
//        printf("Invalid operation!\n");
//    }
//    else{
//        if(s=='+'){
//            printf("%.4lf+%.4lf=%.4lf\n",a,b,a+b);
//        }
//        else if(s=='-'){
//            printf("%.4lf-%.4lf=%.4lf\n",a,b,a-b);
//        }
//        else if(s=='*'){
//            printf("%.4lf*%.4lf=%.4lf\n",a,b,a*b);
//        }
//        else if(s=='/'){
//            if(b==0){
//                printf("Wrong!Division by zero!\n");
//            }
//            else{
//                printf("%.4lf/%.4lf=%.4lf\n",a,b,a/b);
//            }
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0;
//        for(i=0;i<n;i++){
//            printf("*");
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<n;j++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<=i;j++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0;
//        for(i=n;i>0;i--){
//            for(j=0;j<i;j++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<n-i-1;j++){
//                printf("  ");
//            }
//            for(k=n-i-1;k<n;k++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=0;i<n;i++){
//            for(j=n-1;j>i;j--){
//                printf(" ");
//            }
//            for(k=0;k<=i;k++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<i;j++){
//                printf(" ");
//            }
//            for(k=n;k>i;k--){
//                printf("* ");
//            }
//            printf("\n");
//        }
//
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0,l=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<n-i;j++){
//                printf(" ");
//            }
//            for(k=0;k<=i;k++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//        for(l=0;l<n+1;l++){
//            printf("* ");
//        }
//        printf("\n");
//        for(i=0;i<n;i++){
//            for(j=0;j<=i;j++){
//                printf(" ");
//            }
//            for(k=0;k<n-i;k++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//K
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0,l=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<=n-i;j++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//        printf("* \n");
//        for(i=0;i<n;i++){
//            for(j=0;j<=i+1;j++){
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<n-i;j++){
//                printf("  ");
//            }
//            for(k=0;k<=i;k++){
//                printf("*");
//            }
//            printf("\n");
//        }
//        for(i=0;i<=n;i++){
//            printf("*");
//        }
//        printf("\n");
//        for(i=0;i<n;i++){
//            for(j=0;j<=i;j++){
//                printf("  ");
//            }
//            for(k=0;k<n-i;k++){
//                printf("*");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<i;j++){
//                printf(" ");
//            }
//            printf("*\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=0;i<n;i++){
//            for(j=0;j<n-i-1;j++){
//                printf(" ");
//            }
//            printf("*\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        if(n%2==1){
//            int n1=0,i=0,j=0,k=0;
//            n1=(n-1)/2;
//            for(i=0;i<n1;i++){
//                for(j=0;j<i;j++){
//                    printf(" ");
//                }
//                printf("*");
//                for(k=0;k<2*(n1-i)-1;k++){
//                    printf(" ");
//                }
//                printf("*\n");
//            }
//            for(i=0;i<n1;i++){
//                printf(" ");
//            }
//            printf("*\n");
//            for(i=0;i<n1;i++){
//                for(j=0;j<n1-i-1;j++){
//                    printf(" ");
//                }
//                printf("*");
//                for(k=0;k<2*i+1;k++){
//                    printf(" ");
//                }
//                printf("*\n");
//            }
//        }
//        else{
//            int n1=0,i=0,j=0,k=0;
//            n1=(n-2)/2;
//            for(i=0;i<n1;i++){
//                for(j=0;j<i;j++){
//                    printf(" ");
//                }
//                printf("*");
//                for(k=0;k<2*(n1-i);k++){
//                    printf(" ");
//                }
//                printf("*\n");
//            }
//            for(i=0;i<2;i++){
//                for(j=0;j<n1;j++){
//                    printf(" ");
//                }
//                printf("**\n");
//            }
//
//            for(i=0;i<n1;i++){
//                for(j=0;j<n1-i-1;j++){
//                    printf(" ");
//                }
//                printf("*");
//                for(k=0;k<2*(i+1);k++){
//                    printf(" ");
//                }
//                printf("*\n");
//            }
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=0;i<n;i++){
//            printf("* ");
//        }
//        printf("\n");
//        for(i=0;i<n-2;i++){
//            printf("*");
//            for(j=0;j<2*n-3;j++){
//                printf(" ");
//            }
//            printf("*\n");
//        }
//        for(i=0;i<n;i++){
//            printf("* ");
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        printf("* \n");
//        for(i=0;i<n-2;i++){
//            printf("*");
//            for(j=0;j<2*i+1;j++){
//                printf(" ");
//            }
//            printf("* \n");
//        }
//        for(i=0;i<n;i++){
//            printf("* ");
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    printf("Happy New Year*2019*\n");
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    float m=0,sum=0;
//    int i=0;
//    for(i=0;i<5;i++){
//        scanf("%f",&m);
//        sum=sum+m;
//    }
//    printf("%.2f",sum/5);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int score=0;
//    scanf("%d",&score);
//    if(score>=10){
//        printf("Danger++\n");
//    }
//    else if(score>=4&&score<=9){
//        printf("Danger\n");
//    }
//    else{
//        printf("Good\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        switch(n){
//            case 200:printf("OK\n");break;
//            case 202:printf("Accepted\n");break;
//            case 400:printf("Bad Request\n");break;
//            case 403:printf("Forbidden\n");break;
//            case 404:printf("Not Found\n");break;
//            case 500:printf("Internal Server Error\n");break;
//            case 502:printf("Bad Gateway\n");break;
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=1;i<=n;i++){
//            for(j=1;j<=i;j++){
//                printf("%d ",j);
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[7]={0},i=0;
//    while(scanf("%d %d %d %d %d %d %d",&arr[0],&arr[1],&arr[2],&arr[3],&arr[4],&arr[5],&arr[6])!=EOF){
//        float aver=0;
//        int j=0;
//        for(i=0;i<7;i++){
//            for(j=0;j<7-i-1;j++){
//                if(arr[j+1]<arr[j]){
//                    int temp=0;
//                    temp=arr[j];
//                    arr[j]=arr[j+1];
//                    arr[j+1]=temp;
//                }
//            }
//        }
//        for(i=1;i<6;i++){
//            aver=aver+arr[i];
//        }
//        printf("%.2f\n",aver/5);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0;
//    scanf("%d",&n);
//    int arr[50]={0};
//    for(i=0;i<n;i++){
//        scanf("%d ",&arr[i]);
//        if(i==n-1){
//            scanf("%d",&arr[i+1]);
//        }
//    }
//    for(i=0;i<n+1;i++){
//        int j=0,k=0,temp=0;
//        for(j=0;j<n-i;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//            }
//        }
//    }
//    for(i=0;i<n+1;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,arr[100]={0};
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0,k=0;
//        for(i=2;i<=n;i++){
//            arr[i]=i;
//        }
//        for(i=2;i<=n;i++){
//            for(j=2;j<i;j++){
//                if((arr[i]%j==0)&&arr[i]!=0){
//                    k++;
//                    arr[i]=0;
//                }
//            }
//        }
//        for(i=2;i<=n;i++){
//            if(arr[i]!=0){
//                printf("%d ",arr[i]);
//            }
//        }
//        printf("\n%d\n",k);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int row=0,column=0,arr1[100][100]={0},arr2[100][100]={0};
//    scanf("%d %d",&row,&column);
//    int i=0,j=0,k=0;
//    for(i=0;i<row;i++){
//        for(j=0;j<column;j++){
//            scanf("%d ",&arr1[i][j]);
//        }
//    }
//    for(i=0;i<row;i++){
//        for(j=0;j<column;j++){
//            scanf("%d ",&arr2[i][j]);
//        }
//    }
//    for(i=0;i<row;i++){
//        for(j=0;j<column;j++){
//            if(arr1[i][j]==arr2[i][j]){
//                k++;
//            }
//        }
//    }
//    float similarity=k*1.0/(row*column)*100;
//    printf("%.2f",similarity);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char str1[20]={"admin"},str2[20]={"admin"};
//    char str3[20]={0},str4[20]={0};
//    while(scanf("%s  %s",&str3,&str4)!=EOF){
//        int i=0,k=0;
//        for(i=0;i<5;i++){
//            if(str1[i]==str3[i]&&str2[i]==str4[i]){
//                k++;
//            }
//            else{
//                printf("Login Fail!\n");
//            }
//        }
//        if(k==5){
//            printf("Login Success!\n");
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,count=0;
//    for(i=1;i<=2019;i++){
//        if(i%10==9||(i%100)/10==9||(i%1000)/100==9){
//            count++;
//        }
//    }
//    printf("%d",count);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,odd=0,even=0;
//    scanf("%d",&n);
//    int i=0;
//    for(i=1;i<=n;i++){
//        if(i%2==1){
//            odd++;
//        }
//        else{
//            even++;
//        }
//    }
//    printf("%d %d\n",odd,even);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    float arr[100]={0};
//    while(scanf("%d",&n)!=EOF){
//        int i=0,j=0;
//        float k=0;
//        for(i=0;i<n;i++){
//            scanf("%f",&arr[i]);
//            k+=arr[i];
//        }
//        for(i=0;i<n;i++){
//            for(j=0;j<n-i-1;j++){
//                int temp=0;
//                if(arr[j+1]<arr[j]){
//                    temp=arr[j];
//                    arr[j]=arr[j+1];
//                    arr[j+1]=temp;
//                }
//            }
//        }
//        printf("%.2f %.2f %.2f\n",arr[n-1],arr[0],k/n);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0,arr[50]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    arr[n]=k;
//    for(i=0;i<=n;i++){
//        for(j=0;j<=n-i-1;j++){
//            if(arr[j]>arr[j+1]){
//                int temp=0;
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//            }
//        }
//    }
//    for(i=0;i<=n;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[]={1,3,2,4,6,5,7,8,0,9};
//    int i=0,j=0,k=0,flag=1;
//    for(i=0;i<10;i++){
//        int temp=0;
//        for(j=0;j<10-i-1;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=0;
//            }
//        }
//        if(flag){
//            break;
//        }
//    }
//    for(i=0;i<10;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char arr1[100]={0};
//    char arr2[100]={0};
//    scanf("%s",&arr1);
//    scanf("%s",&arr2);
//    int n=sizeof(arr1)/sizeof(char);
//    int i=0,k=0;
//    for(i=0;i<n;i++){
//        if(arr1[i]!=arr2[i]){
//            printf("different\n");
//            break;
//        }
//        else{
//            k++;
//        }
//    }
//    if(k==n){
//        printf("same");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=2,i=0,j=0,k=0,arr1[20]={0},arr2[20]={0},maybe[20]={0};
//    for(i=0;i<n;i++){
//        scanf("%d",&arr1[i]);
//    }
//    for(i=0;i<n;i++){
//        scanf("%d",&arr2[i]);
//    }
//    for(i=0;i<n;i++) {
//        for (j = 0; j < n; j++) {
//                maybe[k] = arr1[i] * arr2[j];
//                k++;
//        }
//    }
//    for(i=0;i<n*n;i++){
//        printf("%d ",maybe[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int N=0,M=0,arr[10][10]={0};
//    int i=0,j=0,k=0;
//    scanf("%d %d",&N,&M);
//    for(i=0;i<N;i++){
//        for(j=0;j<M;j++){
//            scanf("%d",&arr[i][j]);
//            if(arr[i][j]>0){
//                k+=arr[i][j];
//            }
//        }
//    }
//    printf("%d",k);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int i=0,arr[10]={0};
//    for(i=0;i<10;i++){
//        scanf("%d ",&arr[i]);
//    }
//    for(i=0;i<10;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[9]={0},i=0;
//    for(i=0;i<10;i++){
//        scanf("%d ",&arr[i]);
//    }
//    for(i=9;i>=0;i--){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int p=0,n=0,i=0,arr[10]={0};
//    for(i=0;i<10;i++){
//        scanf("%d",&arr[i]);
//        if(arr[i]>0){
//            p++;
//        }
//        if(arr[i]<0){
//            n++;
//        }
//    }
//    printf("positive:%d\nnegative:%d\n",p,n);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int N=0,arr[50]={0},i=0,sum=0;
//    scanf("%d",&N);
//    for(i=0;i<N;i++){
//        scanf("%d ",&arr[i]);
//        sum+=arr[i];
//    }
//    printf("%d",sum);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[10000]={0},n=0,i=0,min=101,max=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//        if(arr[i]>=max){
//            max=arr[i];
//        }
//        if(arr[i]<=min){
//            min=arr[i];
//        }
//    }
//    printf("%d\n",max-min);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,arr[50]={0},i=0,j=0,k=1,l=0,m=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    for(i=0;i<n-1;i++){
//        if(arr[i]>arr[i+1]){
//            l++;
//        }
//        if(arr[i]<arr[i+1]){
//            m++;
//        }
//    }
//    if(l==0||m==0){
//        printf("sorted\n");
//    }
//    else{
//        printf("unsorted\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int i=0,n=5,a=0;
//    for(i=0;i<n;i++){
//        a=1;
//    }
//    printf("%d",i);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int i=0,j=0,k=0,arr[50]={0},n=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&arr[n]);
//    for(i=0;i<n+1;i++){
//        for(j=0;j<n-i;j++){
//            if(arr[j]>arr[j+1]){
//                k=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=k;
//            }
//        }
//    }
//    for(i=0;i<n+1;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[50]={0},brr[50]={0};
//    int n=0,i=0,j=0,k=0,l=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]!=k){
//            brr[j]=arr[i];
//            j++;
//        }
//    }
//    for(i=0;i<j;i++){
//        printf("%d ",brr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[50]={0},brr[50]={0};
//    int n=0,i=0,j=0,k=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]!=k){
//            brr[j]=arr[i];
//            j++;
//        }
//    }
//    for(i=0;i<j;i++){
//        printf("%d ",brr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[50]={0},brr[50]={0};
//    int i=0,n=0,j=0,k=0,l=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]!=k){
//            brr[j]=arr[i];
//            j++;
//        }
//    }
//    for(i=0;i<j;i++){
//        printf("%d ",brr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[50]={0},brr[50]={0};
//    int i=0,j=0,k=0,n=0,l=0,m=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    for(i=0;i<n;i++){
//        l=0;
//        for(j=0;j<i;j++){
//            if(arr[i]==arr[j]){
//                l=1;
//            }
//        }
//        if(l==0){
//            brr[k]=arr[i];
//            k++;
//        }
//    }
//    for(i=0;i<k;i++){
//        printf("%d ",brr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[50]={0},brr[50]={0};
//    int n=0,i=0,j=0,k=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    for(i=0;i<n;i++){
//        int l=0;
//        for(j=0;j<i;j++){
//            if(arr[i]==arr[j]){
//                l=1;
//            }
//        }
//        if(l==0){
//            brr[k]=arr[i];
//            k++;
//        }
//    }
//    for(i=0;i<k;i++){
//        printf("%d ",brr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[1000]={0},brr[1000]={0},crr[2000]={0};
//    int n=0,m=0,i=0,j=0,k=1;
//    scanf("%d %d",&n,&m);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    for(i=0;i<m;i++){
//        scanf("%d",&brr[i]);
//    }
//    for(i=0;i<n+m;i++){
//        if(i<n){
//            crr[i]=arr[i];
//        }
//        else{
//            crr[i]=brr[i-n];
//        }
//    }
//    for(i=0;i<n+m;i++){
//        int temp=0;
//        for(j=0;j<n+m-i-1;j++){
//            if(crr[j]>crr[j+1]){
//                temp=crr[j];
//                crr[j]=crr[j+1];
//                crr[j+1]=temp;
//                k=0;
//            }
//        }
//        if(k){
//            break;
//        }
//    }
//    for(i=0;i<n+m;i++){
//        printf("%d ",crr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    float arr1[5]={0},arr2[5]={0},arr3[5]={0},arr4[5]={0},arr5[5]={0},sum1=0;;
//    float sum2=0,sum3=0,sum4=0,sum5=0;
//    int i=0,j=0,k=0,l=0,m=0,n=0;
//    for(j=0;j<5;j++){
//        scanf("%f",&arr1[j]);
//        sum1+=arr1[j];
//    }
//    for(j=0;j<5;j++){
//        scanf("%f",&arr2[j]);
//        sum2+=arr2[j];
//    }
//    for(j=0;j<5;j++){
//        scanf("%f",&arr3[j]);
//        sum3+=arr3[j];
//    }
//    for(j=0;j<5;j++){
//        scanf("%f",&arr4[j]);
//        sum4+=arr4[j];
//    }
//    for(j=0;j<5;j++){
//        scanf("%f",&arr5[j]);
//        sum5+=arr5[j];
//    }
//    for(i=0;i<5;i++){
//        printf("%.1f ",arr1[i]);
//    }
//    printf("%.1f\n",sum1);
//    for(i=0;i<5;i++){
//        printf("%.1f ",arr2[i]);
//    }
//    printf("%.1f\n",sum2);
//    for(i=0;i<5;i++){
//        printf("%.1f ",arr3[i]);
//    }
//    printf("%.1f\n",sum3);
//    for(i=0;i<5;i++){
//        printf("%.1f ",arr4[i]);
//    }
//    printf("%.1f\n",sum4);
//    for(i=0;i<5;i++){
//        printf("%.1f ",arr5[i]);
//    }
//    printf("%.1f\n",sum5);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    float arr[5][6]={0};
//    int i=0,j=0;
//    for(i=0;i<5;i++){
//        for(j=0;j<5;j++){
//            scanf("%f",&arr[i][j]);
//            arr[i][5]+=arr[i][j];
//        }
//    }
//    for(i=0;i<5;i++){
//        for(j=0;j<=5;j++){
//            printf("%.1f ",arr[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[5][5]={0};
//    int n=0,m=0,i=0,j=0,k=0,l=0;
//    scanf("%d%d",&n,&m);
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&arr[i][j]);
//        }
//    }
//    scanf("%d%d",&n,&m);
//    n-=1;
//    m-=1;
//    printf("%d",arr[n][m]);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,i=0,j=0,k=0;
//    scanf("%d%d",&n,&m);
//    int arr[10][10]={0};
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&arr[i][j]);
//        }
//    }
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            if(j!=m-1){
//                printf("%d ",arr[i][j]);
//            }
//            else{
//                printf("%d\n",arr[i][j]);
//            }
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,i=0,j=0,k=0,o=0,p=0;
//    int arr[10][10]={0};
//    scanf("%d%d",&n,&m);
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&arr[i][j]);
//            if(k<arr[i][j]){
//                k=arr[i][j];
//                o=i+1;
//                p=j+1;
//            }
//        }
//    }
//    printf("%d %d\n",o,p);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[10][10]={0},brr[10][10]={0};
//    int i=0,j=0,k=0,l=0,n=0,m=0;
//    scanf("%d%d",&n,&m);
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&arr[i][j]);
//        }
//    }
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&brr[i][j]);
//        }
//    }
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            if(arr[i][j]==brr[i][j]){
//                k++;
//            }
//        }
//    }
//    if(k==n*m){
//        printf("Yes\n");
//    }
//    else{
//        printf("No\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,i=0,j=0,k=0,l=0;
//    int arr[10][10]={0};
//    scanf("%d",&n);
//    m=n;
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&arr[i][j]);
//            if(i>j){
//                if(arr[i][j]!=0){
//                    k=1;
//                    break;
//                }
//            }
//        }
//    }
//    if(k!=0){
//        printf("NO");
//    }
//    else{
//        printf("YES");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,i=0,j=0,k=0;
//    int arr[10][10]={0};
//    scanf("%d",&n);
//    m=n;
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&arr[i][j]);
//            if(i>j){
//                if(arr[i][j]!=0){
//                    k=1;
//                    break;
//                }
//            }
//        }
//    }
//    if(k==0){
//        printf("YES\n");
//    }
//    else{
//        printf("NO\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,i=0,j=0,k=0;
//    int arr[10][10]={0};
//    scanf("%d%d",&n,&m);
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&arr[i][j]);
//        }
//    }
//    for(i=0;i<m;i++){
//        for(j=0;j<n;j++){
//            printf("%d ",arr[j][i]);
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=2345;
//    char b=0;
//    printf("%-2d\n",a);
//    scanf("%d %c",&a,&b);
//    printf("%d%c",a,b);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,i=0,j=0,k=0,a=0,b=0,temp=0;
//    char t=0;
//    int arr[10][10]={0};
//    scanf("%d%d",&n,&m);
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            scanf("%d",&arr[i][j]);
//        }
//    }
//    scanf("%d",&k);
//    while(k--){
//        getchar();
//        scanf("%c%d%d",&t,&a,&b);
//        a--,b--;
//        if(t=='r'){
//            for(i=0;i<m;i++){
//                temp=arr[b][i];
//                arr[b][i]=arr[a][i];
//                arr[a][i]=temp;
//            }
//        }
//        if(t=='c'){
//            for(i=0;i<n;i++){
//                temp=arr[i][b];
//                arr[i][b]=arr[i][a];
//                arr[i][a]=temp;
//            }
//        }
//    }
//    for(i=0;i<n;i++){
//        for(j=0;j<m;j++){
//            printf("%d ",arr[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0;
//    int arr[30][30]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        for(j=0;j<i+1;j++){
//            if(j==0||j==i){
//                arr[i][j]=1;
//            }
//            else{
//                arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
//            }
//        }
//    }
//    for(i=0;i<n;i++){
//        for(j=0;j<i+1;j++){
//            printf("%5d",arr[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int i=0,j=0,k=0;
//    char arr[3][3]={0};
//    for(i=0;i<3;i++){
//        for(j=0;j<3;j++){
//            scanf(" %c",&arr[i][j]);
//        }
//    }
//    for(i=0;i<3;i++){
//        for(j=0;j<3;j++){
//            if(arr[i][j-2]=='K'&&arr[i][j-1]=='K'&&arr[i][j]=='K'){
//                printf("KiKi wins!\n");
//                goto END;
//            }
//            else if(arr[i-2][j]=='K'&&arr[i-1][j]=='K'&&arr[i][j]=='K'){
//                printf("KiKi wins!\n");
//                goto END;
//            }
//            else if(arr[i-2][j-2]=='K'&&arr[i-1][j-1]=='K'&&arr[i][j]=='K'){
//                printf("KiKi wins!\n");
//                goto END;
//            }
//            else if(arr[i-2][j]=='K'&&arr[i-1][j-1]=='K'&&arr[i][j-2]=='K'){
//                printf("KiKi wins!\n");
//                goto END;
//            }
//            else if(arr[i][j-2]=='B'&&arr[i][j-1]=='B'&&arr[i][j]=='B'){
//                printf("BoBo wins!\n");
//                goto END;
//            }
//            else if(arr[i-2][j]=='B'&&arr[i-1][j]=='B'&&arr[i][j]=='B'){
//                printf("BoBo wins!\n");
//                goto END;
//            }
//            else if(arr[i-2][j-2]=='B'&&arr[i-1][j-1]=='B'&&arr[i][j]=='B'){
//                printf("BoBo wins!\n");
//                goto END;
//            }
//            else if(arr[i-2][j]=='B'&&arr[i-1][j-1]=='B'&&arr[i][j-2]=='B'){
//                printf("BoBo wins!\n");
//                goto END;
//            }
//        }
//    }
//    printf("No winner!\n");
//    END:
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,i=1;
//    scanf("%d",&n);
//    while(n){
//        m=m+(n%6)*i;
//        n=n/6;//在六进制数中去掉最后一位
//        i=i*10;
//    }
//    printf("%d",m);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,m=0,i=0;
//    scanf("%ld",&n);
//    for(i=1;i<n+1;i++){
//        m+=i;
//    }
//    printf("%ld",m);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long hour=0,minute=0,k=0,h1=0,m1=0,h2=0,m2=0;
//    scanf("%ld:%ld%ld",&hour,&minute,&k);
//    h1=k/60;
//    if(h1+hour>24){
//        h2=(h1+hour)%24;
//    }
//    else{
//        h2=h1+hour;
//    }
//    m1=k%60;
//    if(m1+minute>60){
//        m2=(m1+minute)%60;
//        h2++;
//    }
//    else{
//        m2=m1+minute;
//    }
//    printf("%02ld:%02ld",h2,m2);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long hour=0,minute=0,k=0,h1=0,m1=0;
//    scanf("%ld:%ld%ld",&hour,&minute,&k);
//    h1=(hour+(k+minute)/60)%24;
//    m1=(minute+k%60)%60;
//    printf("%02ld:%02ld",h1,m1);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long hour=0,minute=0,k=0,h1=0,m1=0;
//    scanf("%ld:%ld%ld",&hour,&minute,&k);
//    h1=(hour+(k+minute)/60)%24;
//    m1=(minute+k)%60;
//    printf("%02ld:%02ld",h1,m1);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,k=0,time=0;
//    scanf("%ld",&n);
//    k=n/12*4;
//    printf("%ld",k+2);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=1,b=0;
//    while(a-1){
//        a--;
//        printf("Yes\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,m=0,p=0,q=0,k1=0,k2=0,temp=0;
//    scanf("%ld%ld",&n,&m);
//    p=n;
//    q=m;
//    if(n>m){
//        temp=n;
//        n=m;
//        m=temp;
//    }
//    while(m%n){
//        m=m%n;
//        if(m<n){
//            temp=n;
//            n=m;
//            m=temp;
//        }
//    }
//    k1=n;
//    k2=p*q/k1;
//    printf("%ld",k1+k2);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,m=0,p=0,q=0,k1=0,k2=0,temp=0;
//    scanf("%ld%ld",&n,&m);
//    if(n>m){
//        temp=n;
//        n=m;
//        m=temp;
//    }
//    p=n;
//    q=m;
//    while(m%n){
//        m=m%n;//最后一次这个m会变成0,如果把n和m互换，那么k1得到的就是互换后的n，也就是互换前的m，0，
//        if(m<n){
//            temp=n;
//            n=m;
//            m=temp;
//        }
//    }
//    k1=n;
//    k2=p*q/k1;
//    printf("%ld",k1+k2);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,i=1,m=0;
//    scanf("%ld",&n);
//    while(n){
//        m=m+n%6*i;
//        i*=10;
//        n/=6;
//    }
//    printf("%ld",m);
//    return 0;
//}
//#include<stdio.h>
//long FX(long n,long i,long m){
//    if(n){
//        m=n%6*i+m;
//        return FX(n/6,i*10,m);
//    }
//    return m;
//}
//int main(){
//    long n=0,m=0,i=1;
//    scanf("%ld",&n);
//    printf("%ld",FX(n,i,m));
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,i=1,m=0;
//    scanf("%ld",&n);
//    while(n){
//        m=n%6*i+m;
//        n=n/6;
//        i=i*10;
//    }
//    printf("%ld",m);
//    return 0;
//}
//#include<stdio.h>
//long FX(long n,long m,long i){
//    if(n){
//        m+=n%6*i;
//        return FX(n/6,m,i*10);
//    }
//    return m;
//}
//int main(){
//    long n=0,m=0,i=1;
//    scanf("%ld",&n);
//    printf("%ld",FX(n,m,i));
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,r=0,i=1,k=0;
//    scanf("%ld",&n);
//    while(n){
//        if(n%2==0){
//            k=0;
//        }
//        else{
//            k=1;
//        }
//        r=r+k*i;
//        n/=10;
//        i=i*10;
//    }
//    printf("%ld",r);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,i=1,k=0,r=0;
//    scanf("%ld",&n);
//    while(n){
//        if(n%2==0){
//            k=0;
//        }
//        else{
//            k=1;
//        }
//        r+=k*i;
//        n/=10;
//        i=i*10;
//    }
//    printf("%ld",r);
//    return 0;
//}
//#include<stdio.h>
//long RE(long n,long i,long r){
//    long k=0;
//    if(n%2==0){
//        k=0;
//    }
//    else{
//        k=1;
//    }
//    r=k*i;
//    if(n){
//        return RE(n/10,i*10,r)+r;
//    }
//    return r;
//}
//int main(){
//    long n=0,i=1,k=0,r=0;
//    scanf("%ld",&n);
//    printf("%ld",RE(n,i,r));
//    return 0;
//}
//#include<stdio.h>
//long CH(long n,long i,long r){
//    long k=0;
//    if(n%2==0){
//        k=0;
//    }
//    else{
//        k=1;
//    }
//    r=k*i;
//    if(n){
//        return CH(n/=10,i*10,r)+r;
//    }
//    return r;
//}
//int main(){
//    long n=0,i=1,k=0,r=0;
//    scanf("%ld",&n);
//    printf("%ld",CH(n,i,r));
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,i=1,k=0,r=0;
//    scanf("%ld",&n);
//    while(n){
//        if(n%2==0){
//            k=0;
//        }
//        else{
//            k=1;
//        }
//        r+=k*i;
//        i*=10;
//        n/=10;
//    }
//    printf("%ld",r);
//    return 0;
//}
//#include<stdio.h>
//int FX(int n){
//    if(n==1||n==2){
//        return n;
//    }
//    return FX(n-1)+FX(n-2);
//}
//int main(){
//    int n=0,k=0,i=0;
//    scanf("%d",&n);
//    printf("%d",FX(n));
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=1,temp=0;
//    int arr[50]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    for(i=0;i<n-1;i++){
//        for (j = 0;  j<n-i-1 ; j++) {
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                k=0;
//            }
//        }
//        if(k){
//            break;
//        }
//    }
//    for(i=0;i<n;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,i=0,j=0,k=0,l=0,temp=0;
//    long arr[100000]={0};
//    scanf("%ld",&n);
//    for(i=0;i<n;i++){
//        scanf("%ld",&arr[i]);
//    }
//    for(i=0;i<n-1;i++){
//        for(j=0;j<n-i-1;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                k=1;
//            }
//        }
//        if(k==0){
//            break;
//        }
//    }
//    for(i=0;i<n;i++){
//        if(arr[i]!=arr[i+1]){
//            printf("%ld ",arr[i]);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0,l=0,temp=0;
//    int arr[100000]={0};
//    scanf("%d",&n);
//    while(scanf("%d",&temp)!=EOF){
//        arr[temp]++;
//    }
//    for(i=0;i<n;i++){
//        if(arr[i]!=0){
//            printf("%d ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,temp=0;
//    int arr[100000]={0};
//    scanf("%d",&n);
//    for(i=1;i<=n;i++){
//        scanf("%d",&temp);
//        arr[temp]++;
//    }
//    for(i=0;i<n;i++){
//        if(arr[i]){
//            printf("%d ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char s[8000]={0};
//    scanf("%s",s);
//    long long c=0;
//    long long ch=0;
//    long long chn=0;
//    char *p=s;
//    while(*p){
//        if(*p=='C'){
//            c++;
//        }
//        else if(*p=='H'){
//            ch+=c;
//        }
//        else if(*p=='N'){
//            chn+=ch;
//        }
//        p++;
//    }
//    printf("%lld",chn);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,temp=0;
//    int arr[100000]={0};
//    scanf("%d",&n);
//    int i=0;
//    for(i=1;i<100001;i++){
//        scanf("%d",&temp);
//        arr[temp]=temp;
//    }
//    for(i=0;i<n;i++){
//        if(arr[i]){
//            printf("%d ",arr[i]);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,temp=0;
//    int arr[100000]={0};
//    scanf("%d",&n);
//    while(scanf("%d",&temp)!=EOF){
//        getchar();
//        arr[temp]++;
//    }
//    for(i=0;i<n;i++){
//        if(arr[i]){
//            printf("%d ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,temp=0;
//    int arr[100000]={0};
//    scanf("%d",&n);
//    while(scanf("%d",&temp)!=EOF){
//        getchar();
//        arr[temp]++;
//    }
//    for(i=0;i<n;i++){
//        if(arr[i]){
//            printf("%d ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//typedef long long ll;
//int main(){
//    char s[8000]={0};
//    scanf("%s",s);
//    ll c=0,ch=0,chn=0;
//    char* p=s;
//    while(*p){
//        if(*p=='C'){
//            c++;
//        }
//        else if(*p=='H'){
//            ch+=c;
//        }
//        else if(*p=='N'){
//            chn+=ch;
//        }
//        p++;
//    }
//    printf("%lld",chn);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,temp=0;
//    int arr[100000]={0};
//    scanf("%d",&n);
//    while(scanf("%d",&temp)!=EOF){
//        getchar();
//        arr[temp]++;
//    }
//    int i=0;
//    for(i=0;i<100001;i++){
//        if(arr[i]){
//            printf("%d ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//typedef long long ll;
//int main(){
//    char s[8000]={0};
//    scanf("%s",s);
//    char* p=s;
//    ll c=0,ch=0,chn=0;
//    while(*p){
//        if(*p=='C'){
//            c++;
//        }
//        else if(*p=='H'){
//            ch+=c;
//        }
//        else if(*p=='N'){
//            chn+=ch;
//        }
//        p++;
//    }
//    printf("%lld",chn);
//    return 0;
//}
//#include<stdio.h>
//int FX(int n){
//    if(n<=2){
//        return n;
//    }
//    else{
//        return FX(n-1)+FX(n-2);
//    }
//}
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    printf("%d",FX(n));
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    int FX(int n);
//    printf("%d",FX(n));
//    return 0;
//}
//int FX(int n){
//    if(n<=2){
//        return n;
//    }
//    else{
//        return FX(n-1)+FX(n-2);
//    }
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0;
//    int arr[5]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    int temp=0;
//    for(i=0;i<n-1;i++){
//        for(j=0;j<n-i-1;j++){
//            if(arr[j]<arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//            }
//        }
//    }
//    for(i=0;i<n;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int arr[5]={0};
//    int i=0,j=0,temp=0;
//    int n=5;
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    int flag=1;
//    for(i=0;i<n-1;i++){
//        for(j=0;j<n-1-i;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//                flag=0;
//            }
//        }
//        if(flag){
//            break;
//        }
//    }
//    for(i=0;i<n;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>//阶乘,递归
//int fact(int n){
//    if(n<=1){
//        return n;
//    }
//    else{
//        return n*fact(n-1);
//    }
//}
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    printf("%d",fact(n));
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    int fact(int n);
//    printf("%d",fact(n));
//    return 0;
//}
//int fact(int n){
//    if(n<=1){
//        return n;
//    }
//    else{
//        return n*fact(n-1);
//    }
//}
//#include<stdio.h>
//int fact(int n){
//    if(n<=1){
//        return n;
//    }
//    else{
//        return n*fact(n-1);
//    }
//}
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    printf("%d",fact(n));
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    int fact(int n);
//    printf("%d",fact(n));
//    return 0;
//}
//int fact(int n){
//    if(n<=1){
//        return n;
//    }
//    else{
//        return n*fact(n-1);
//    }
//}
//#include<stdio.h>//桶排序1,不多次运行;把重复数字删除，只留一个
//int main(){
//    int arr[20]={0};
//    int n=0,i=0,j=0,k=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&k);
//        arr[k]++;
//    }
//    for(i=0;i<20;i++){
//        if(arr[i]){
//            printf("%d",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>//桶排序1.2,不多次运行;把重复数字删除，只留一个
//int main(){
//    int arr[20]={0};
//    int n=0,i=0,k=0;
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&k);
//        arr[k]++;
//    }
//    for(i=0;i<20;i++){
//        if(arr[i]){
//            printf("%d ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>//桶排序，多次使用
//int main(){
//    int arr[100]={0};
//    int n=0,i=0,k=0;
//    while(scanf("%d",&n)!=EOF){
//        for(i=0;i<n;i++){
//            scanf("%d",&k);
//            arr[k]++;
//        }
//        for(i=0;i<100;i++){
//            if(arr[i]){
//                printf("%d ",i);
//            }
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>//桶排序,多次使用1.2
//int main(){
//    int arr[100]={0};
//    int n=0,i=0,k=0;
//    while(scanf("%d",&n)!=EOF){
//        for(i=0;i<n;i++){
//            scanf("%d",&k);
//            arr[k]++;
//        }
//        for(i=0;i<100;i++){
//            if(arr[i]){
//                printf("%d ",i);
//            }
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,m=0,max=0,min=0,temp=0,p=0,q=0;
//    scanf("%ld %ld",&n,&m);
//    p=m,q=n;
//    while(m%n){
//        m=m%n;
//        if(m<n){
//            temp=m;
//            m=n;
//            n=temp;
//        }
//    }
//    max=n;
//    min=p*q/max;
//    printf("%ld",min+max);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long m=0,n=0,max=0,min=0,p=0,q=0;
//    scanf("%ld %ld",&m,&n);
//    p=m,q=n;
//    long temp=0;
//    while(m%n){
//        m=m%n;
//        if(m<n){
//            temp=n;
//            n=m;
//            m=temp;
//        }
//    }
//    max=n;
//    min=p*q/max;
//    printf("%ld",max+min);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,m=0;
//    scanf("%ld %ld",&n,&m);
//    long max=0,min=0;
//    long p=m,q=n;
//    while(m%n){
//        m=m%n;
//        long temp=0;
//        if(m<n){
//            temp=n;
//            n=m;
//            m=temp;
//        }
//    }
//    max=n;
//    min=p*q/max;
//    printf("%ld",max+min);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=0,b=0;
//    a=1;
//    b=2;
//    a=a+b,b=a-b,a=a-b;
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    int DG(int n);
//    printf("%d",DG(n));
//    return 0;
//}
//int DG(int n){
//    if(n<=2){
//        return n;
//    }
//    else{
//        return DG(n-1)+DG(n-2);
//    }
//}
//#include<stdio.h>
//typedef long long ll;
//int main(){
//    char arr[8000]={0};
//    ll c=0,ch=0,chn=0;
//    scanf("%s",&arr);
//    char *p=arr;
//    while(*p){
//        if(*p=='C'){
//            c++;
//        }
//        else if(*p=='H'){
//            ch+=c;
//        }
//        else if(*p=='N'){
//            chn+=ch;
//        }
//        *p++;
//    }
//    printf("%lld\n",chn);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,x=0;
//    int k=0,arr[100]={0};
//    scanf("%d",&n);
//    int i=0;
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&x);
//    int count=0;
//    for(i=0;i<n;i++){
//        if(arr[i]==x){
//            count++;
//        }
//    }
//    printf("%d",count);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,x=0;
//    int arr[100]={0};
//    scanf("%d",&n);
//    int i=0,k=0;
//    for(i=0;i<n;i++){
//        scanf("%d",&k);
//        arr[k]++;
//    }
//    scanf("%d",&x);
//    printf("%d",arr[x]);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,x=0;
//    int arr[100]={0};
//    scanf("%d",&n);
//    int i=0,k=0;
//    for(i=0;i<n;i++){
//        scanf("%d",&k);
//        arr[k]++;
//    }
//    scanf("%d",&x);
//    printf("%d",arr[x]);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,k=0,i=0;
//    long arr[100000]={0};
//    scanf("%ld",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&k);
//        arr[k]++;
//    }
//    for(i=0;i<100000;i++){
//        if(arr[i]){
//            printf("%ld ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,x=0,k=0;
//    long arr[100000]={0};
//    scanf("%ld",&n);
//    long i=0;
//    for(i=0;i<n;i++){
//        scanf("%ld",&k);
//        arr[k]++;
//    }
//    for(i=0;i<100000;i++){
//        if(arr[i]){
//            printf("%ld ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,x=0,i=0;
//    long arr[100000]={0};
//    scanf("%ld",&n);
//    long k=0;
//    for(i=0;i<n;i++){
//        scanf("%ld",&k);
//        arr[k]++;
//    }
//    for(i=0;i<100000;i++){
//        if(arr[i]){
//            printf("%ld ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    long n=0,k=0,i=0;
//    long arr[100000]={0};
//    scanf("%ld",&n);
//    for(i=0;i<n;i++){
//        scanf("%ld",&k);
//        arr[k]++;
//    }
//    for(i=0;i<100000;i++){
//        if(arr[i]){
//            printf("%ld ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    printf("printf(\"Hello world!\\n\");\n");
//    printf("cout << \"Hello world!\" << endl;");
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    float a1=0,a2=0,a3=0,a4=0;
//    int i=0;
//    scanf("%f%f%f%f",&a1,&a2,&a3,&a4);
//    printf("%.1f",a1*0.2+a2*0.1+a3*0.2+a4*0.5);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    int i=0;
//    for(i=0;i<n;i++){
//        printf("Happy new year!Good luck!\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int max1(int a,int b,int c){
//    int x=0,y=0;
//    x=a>b?a:b;
//    y=b>c?b:c;
//    return x>y?x:y;
//}
//int main(){
//    int a=0,b=0,c=0;
//    scanf("%d%d%d",&a,&b,&c);
//    printf("%d",max1(a,b,c));
//    return 0;
//}
//#include<stdio.h>
//int judge1(int n){
//    int i=0;
//    for(i=2;i<n/2;i++){
//        if(n%i){
//            continue;
//        }
//        else{
//            return 1;
//        }
//    }
//    return 0;
//}
//int main(){
//    int n=100,m=999;
//    int count=0;
//    for(n;n<=m;n++){
//        if(judge1(n)==0){
//            count++;
//        }
//    }
//    printf("%d",count);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0,i=0;
//    n=100,m=999;
//    int count=0,j=0,k=0;
//    for(n;n<=m;n++){
//        k=1;
//        for(j=2;j<=n/2;j++){
//            if(n%j==0){
//                k=0;
//            }
//        }
//        if(k){
//            count++;
//        }
//    }
//    printf("%d",count);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,m=0;
//    n=100,m=999;
//    int i=0,k=0,j=0,count=0;
//    for(n;n<=m;n++){
//        k=1;
//        for(j=2;j<=n/2;j++){
//            if(n%j==0){
//                k=0;
//            }
//        }
//        if(k){
//            count++;
//        }
//    }
//    printf("%d",count);
//    return 0;
//}
//#include<stdio.h>
//int f(int n){
//    int i=0,k=0;
//    for(i=2;i<=n/2;i++){
//        if(n%i==0){
//            return 0;
//        }
//    }
//    return 1;
//}
//int main(){
//    int n=100,count=0,m=999;
//    for(n;n<=m;n++){
//        if(f(n)){
//            count++;
//        }
//    }
//    printf("%d",count);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=100,m=999;
//    int i=0,j=0,k=0;
//    for(n;n<=m;n++){
//        k=0;
//        for(i=2;i<=n/2;i++){
//            if(n%i==0){
//                k=1;
//            }
//        }
//        if(k==0){
//            j++;
//        }
//    }
//    printf("%d",j);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,k=0;
//    scanf("%d",&n);
//    int arr[1001]={0};
//    int i=0;
//    for(i=0;i<n;i++){
//        scanf("%d",&k);
//        arr[k]++;
//    }
//    for(i=1;i<1001;i++){
//        if(arr[i]){
//            printf("%d ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,k=0,i=0;
//    int arr[1001]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&k);
//        arr[k]++;
//    }
//    for(i=1;i<1001;i++){
//        if(arr[i]){
//            printf("%d ",i);
//        }
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,j=0,count=0;
//    scanf("%lld",&n);
//    ll arr[10][10]={0};
//    for(i=0;i<n;i++){
//        for(j=0;j<n;j++){
//            scanf("%lld",&arr[i][j]);
//            if(i>j){
//                if(arr[i][j]==0){
//                    count++;
//                }
//            }
//        }
//    }
//    ll sum=0;
//    sum=(n*(n-1))/2;
//    if(sum==count){
//        printf("YES\n");
//    }
//    else{
//        printf("NO\n");
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,j=0,count=0;
//    ll arr[10][10]={0};
//    scanf("%lld",&n);
//    for(i=0;i<n;i++){
//        for(j=0;j<n;j++){
//            scanf("%lld",&arr[i][j]);
//            if(i>j){
//                if(arr[i][j]==0){
//                    count++;
//                }
//            }
//        }
//    }
//    ll sum=0;
//    sum=(n*(n-1))/2;
//    if(sum==count){
//        printf("YES");
//    }
//    else{
//        printf("NO");
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,j=0,count=0;
//    ll arr[10][10]={0};
//    scanf("%lld",&n);
//    for(i=0;i<n;i++){
//        for(j=0;j<n;j++){
//            scanf("%lld",&arr[i][j]);
//            if(i>j){
//                if(arr[i][j]==0){
//                    count++;
//                }
//            }
//        }
//    }
//    ll sum=0;
//    sum=(n*(n-1))/2;
//    if(sum==count){
//        printf("YES\n");
//    }
//    else{
//        printf("NO\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0;
//    int arr[51]={0},brr[51]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    int del=0;
//    scanf("%d",&del);
//    for(i=0;i<n;i++){
//        if(arr[i]!=del){
//            brr[j]=arr[i];
//            j++;
//        }
//    }
//    for(i=0;i<j;i++){
//        printf("%d ",brr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0;
//    int arr[51]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]!=k){
//            printf("%d ",arr[i]);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0;
//    int arr[51]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]==k){
//            continue;
//        }
//        else{
//            printf("%d ",arr[i]);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0;
//    int arr[51]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    int count=0;
//    for(i=0;i<n;i++){
//        if(arr[i]==k){
//            for(j=i;j<n;j++){
//                arr[j]=arr[j+1];
//            }
//            count++;
//            i--;
//        }
//    }
//    for(i=0;i<n-count;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0;
//    int arr[51]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    int count=0;
//    for(i=0;i<n;i++){
//        if(arr[i]==k){
//            for(j=i;j<n;j++){
//                arr[j]=arr[j+1];
//            }
//            count++;
//            i--;
//        }
//    }
//    for(i=0;i<n-count;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0,count=0;
//    int arr[51]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]==k){
//            for(j=i;j<n;j++){
//                arr[j]=arr[j+1];
//            }
//            count++;
//            i--;
//        }
//    }
//    for(i=0;i<n-count;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0,count=0;
//    int arr[51]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]==k){
//            for(j=i;j<n;j++){
//                arr[j]=arr[j+1];
//            }
//            count++;
//            i--;
//        }
//    }
//    for(i=0;i<n-count;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int n=0,i=0,j=0,k=0,count=0;
//    int arr[51]={0},brr[51]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]!=k){
//            brr[j]=arr[i];
//            j++;
//        }
//    }
//    for(i=0;i<j;i++){
//        printf("%d ",brr[i]);
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,j=0,k=0;
//    ll arr[101]={0};
//    scanf("%lld",&n);
//    for(i=0;i<n;i++){
//        scanf("%lld",&arr[i]);
//    }
//    scanf("%lld",&k);
//    ll count=0;
//    for(i=0;i<n;i++){
//        if(arr[i]==k){
//            for(j=i;j<n;j++){
//                arr[j]=arr[j+1];
//            }
//            count++;
//            i--;
//        }
//    }
//    printf("%lld\n",n-count);
//    for(i=0;i<n-count;i++){
//        printf("%lld ",arr[i]);
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,j=0,count=0,k=0;
//    ll arr[101]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    scanf("%d",&k);
//    for(i=0;i<n;i++){
//        if(arr[i]==k){
//            for(j=i;j<n;j++){
//                arr[j]=arr[j+1];
//            }
//            count++;
//            i--;
//        }
//    }
//    printf("%d\n",n-count);
//    for(i=0;i<n-count;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll month=0,year=0,day=0;
//    scanf("%lld%lld%lld",&year,&month,&day);
//    printf("%lld/%lld/%lld",day,month,year);
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,k=0,i=0,length=0,width=0,radius=0,side=0;
//    scanf("%lld%lld",&length,&width);
//    scanf("%lld",&radius);
//    scanf("%lld",&side);
//    printf("%lld\n%g\n%lld\n",length*width,3.14*radius*radius,side*side);
//    return 0;
//}
//#include<stdio.h>//递归，阶乘
//int fact(int n){
//    if(n<=2){
//        return n;
//    }
//    else{
//        return n*fact(n-1);
//    }
//}
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    printf("%d",fact(n));
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,j=0,k=0;
//    ll arr[100001]={0};
//    scanf("%lld",&n);
//    for(i=0;i<n;i++){
//        scanf("%lld",&k);
//        arr[k]++;
//    }
//    for(i=0;i<100001;i++){
//        if(arr[i]){
//            printf("%lld ",i);
//        }
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,k=0;
//    ll arr[100001]={0};
//    scanf("%lld",&n);
//    for(i=0;i<n;i++){
//        scanf("%lld",&k);
//        arr[k]++;
//    }
//    for(i=0;i<100001;i++){
//        if(arr[i]){
//            printf("%lld ",i);
//        }
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,k=0;
//    ll arr[100001]={0};
//    scanf("%lld",&n);
//    for(i=0;i<n;i++){
//        scanf("%lld",&k);
//        arr[k]++;
//    }
//    for(i=0;i<n;i++){
//        if(arr[i]){
//            printf("%lld ",i);
//        }
//    }
//    return 0;
//}
//#include<stdio.h>//冒泡排序，优化版,升序
//int main(){
//    int n=0,j=0,i=0,flag=0;
//    int arr[20]={0};
//    scanf("%d",&n);
//    for(i=0;i<n;i++){
//        scanf("%d",&arr[i]);
//    }
//    for(i=0;i<n-1;i++){
//        int temp=0;
//        for(j=0;j<n-1-i;j++){
//            if(arr[j]>arr[j+1]){
//                temp=arr[j];
//                arr[j]=arr[j+1];
//                arr[j+1]=temp;
//            flag=1;
//            }
//        }
//        if(flag==0){
//            break;
//        }
//    }
//    for(i=0;i<n;i++){
//        printf("%d ",arr[i]);
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,k=0;
//    ll arr[100001]={0};
//    scanf("%lld",&n);
//    for(i=0;i<n;i++){
//        scanf("%lld",&k);
//        arr[k]++;
//    }
//    for(i=0;i<100001;i++){
//        if(arr[i]){
//            printf("%lld ",i);
//        }
//    }
//    return 0;
//}
//typedef long long ll;
//#include<stdio.h>
//int main(){
//    ll n=0,i=0,k=0;
//    ll arr[100001]={0};
//    scanf("%lld",&n);
//    for(i=0;i<n;i++){
//        scanf("%lld",&k);
//        arr[k]++;
//    }
//    for(i=0;i<100001;i++){
//        if(arr[i]){
//            printf("%lld ",i);
//        }
//    }
//    return 0;
//}
//#inlcude<stdio.h>//阶乘
//int fact(int n){
//    if(n<=2){
//        return n;
//    }
//    else{
//        return n*fact(n-1);
//    }
//}
//int main(){
//    int n=0;
//    sacnf("%d",&n);
//    printf("%d",fact(n));
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=0,b=0;
//    a=33;
//    b=33;
//    printf("%+d,%-d",a,b);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=0,b=0;
//    scanf("%d,%d",&a,&b);
//    printf("%d,%d",a,b);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    float pi=3.1416;
//    float a=123.456;
//    float d1=-3.5;
//    double a=3.1415926;
//    printf("%14f",pi);
//printf("%-14.10lf",a);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a=1,c=2;
//    float b=1.0,x;
//    char c1,c2;
////    scanf("%d%f%f%c%c",&a,&b,&x,&c1,&c2);
//scanf("%x%*d%o",&a,&b);
//    printf("%x %*d",a,b,c);
//    return 0;
//}
//#include<stdio.h>
//#include<math.h>
//int main(){
//    float d1=3.5,d2=-3.5;
//    printf("(1)%e|(2)%4e|(3)%10.4e\n(4)%e|(5)%6e|(6)%-12.5e",d1,d1,d1,d2,d2,d2);
//    int arr[10];
//    arr[10-2]=1;
//    int arr[10 ];
//    arr[9 ]=1;
//    int i,t=1,s=0;
//    while(x1){
//float n=0,sum=0;
//int i=0;
//for(i=0,n=2;n<=100;i++){
//    sum+=n*0.8;
//    n*=2;
//}
//printf("%f",sum/i);
//        x2= x1/2-2;
//        x1=x2;
//        x++;
//    }
//    printf("%d",x);
//    while(1){
//        printf("%d",x++);
//        printf("%d",x);
//        break;
//    }
//for(int i=0;i<3&&i>0;i++){
//    printf("%d ",i);
//}
//    return 0;
//}
//#include<stdio.h>//a[3][5]
//int main()
//{
//    int a=0;
//    a=sizeof("ab\n\\012\\\"");
//    printf("%d",a);
//int a[8]={0,1,2,3,4,5,6,7};
//int b[2][4]={0};
//int i=0,j=0;
//for(i=0;i<2;i++){
//    for(j=0;j<4;j++){
//        b[i][j]=a[4*i+j];
//    }
//}
//printf("%d",b[1][3]);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    char p[100]={0};
//    char q[100]={0};
//    char*p1,*p2;
//    int m=0;
//    scanf("%s",p);
//    scanf("%s %d",q,&m);
//    p1=p,p2=q;
//    void copyy(char*p1,char*p2,int m);
//    copyy(p1,p2,m);
//    printf("%s",p);
//    return 0;
//}
//void copyy(char*p1,char*p2,int m){
//    int i=0,j=0,k=m-1;
//    for(i=k,j=0;*(p2+j)!='\0';i++,j++)
//        *(p1+i)=*(p2+j);
//        *(p1+i)='\0';
//}
//#include<stdio.h>
//int main(){
//    int a[10]={0};
//    int i=0;
//    int *q;
//    printf("请输入原数组:\n");
//    for(i=0;i<10;i++){
//        scanf("%d",&a[i]);
//    }
//    q=a;
//    int k=0;
//    int n=0;
//    printf("逆序起始位置与逆序位数:\n");
//    scanf("%d %d",&k,&n);
//    int j=0,flag=1,t=0;
//    for(i=0;i<n-1;i++){
//        for(j=k-1;j<n+k-2-i;j++){
//            if((*(q+j))<(*(q+j+1))){
//                t=*(q+j);
//                *(q+j)=*(q+j+1);
//                *(q+j+1)=t;
//                flag=0;
//            }
//        }
//        if(flag){
//            break;
//        }
//    }
//    for(i=0;i<10;i++){
//        printf("%d ",a[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int *p[6];
//    int a[6]={2,4,6,8,10,12};
//    int i=0,j=0,t=2;
//    p[0]=a;
//    for(i=0;i<3;i++){
//        for(j=0;j<2;j++){
//            p[i][j]=t;
//            t+=2;
//        }
//    }
//    for(j=0;j<2;j++){
//        for(i=0;i<3;i++){
//            printf("%d ",p[i][j]);
//        }
//        printf("\n");
//    }
//    for(i=0;i<3;i++){
//        for(j=0;j<2;j++){
//            printf("%d ",p[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    float sum=0;//检查小数是否是对的
//    float a[21]={0};
//    a[0]=1,a[1]=2;
//    int i=0;
//    for(i=2;i<21;i++)
//        a[i]=a[i-1]+a[i-2];
//    for(i=1;i<21;i++)
//        sum=sum+a[i]/a[i-1];
//    printf("%.2f",sum);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a[20]={0};
//    int i=0;
//    for(i=0;i<20;i++)
//        scanf("%d",&a[i]);//千万别忘了加取地址符号
//    int max=0,max1=0;
//    max=max1=a[0];
//    for(i=1;i<20;i++)
//        if(a[i]>max)
//            max=a[i];
//        for(i=0;i<20;i++)
//            if((a[i]>max1)&&(a[i]!=max))
//                max1=a[i];
//            printf("最大值:%d,次大值:%d",max,max1);
//    return 0;
//}
//#include<stdio.h>
//void main(){
//    int a=4,b=3,c=2,t=0;
//    if(b>a&&a<c)t=a;a=c;c=t;
//    printf("%d",c);
//}
//#include<stdio.h>
//int main(){
//    int i=0,sum=0;
//    for(i=1;i<101;i++){
//        sum=sum+i;
//    }
//    printf("%d",sum);
//    return 0;
//}
//#include<stdio.h>
//int su(int a){
//    int i=0;int flag=0;
//    for(i=2;i<=a/2;i++){
//        if(a%i==0){
//            flag=1;
//            return flag;}
//    }
//    return flag;
//}
//int main(){
//    int a=100;
//    int k=0;
//    printf("素数有:\n");
//    for(a=100;a<=200;a++){
//        if(su(a)==0){
//            printf("%d ",a);}
//    }
//    return 0;
//}
//#include<stdio.h>
//void maxx(int a[3][4]){
//    int h=0,l=0;
//    int max=0;max=a[0][0];
//    int i=0,j=0;
//    for(i=0;i<3;i++)
//        for(j=0;j<4;j++){
//            if(a[i][j]>max){
//                max=a[i][j];
//                h=i;
//                l=j;
//            }
//        }
//    printf("max=%d,h=%d,l=%d",max,h,l);
//}
//int main(){
//    int a[3][4]={61,34,7,33,80,46,0,35,9,21,48,16};
//    maxx(a);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int i=0,j=0;
//    for(i=1;i<10;i++){
//        for(j=1;j<i+1;j++)
//            printf("%d*%d=%d ",i,j,i*j);
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//int su(int a){
//    int i=2;int flag=1;
//    for(i=2;i<=a/2;i++){
//        if(a%i==0){
//            flag=0;
//            return flag;
//        }
//    }
//    return flag;
//}
//int main(){
//    int i=2;int sum=0;
//    for(i=2;i<=500;i++){
//        if(su(i)){
//            sum+=i;
//            printf("%d为素数\n",i);
//        }
//    }
//    printf("素数总和为%d\n",sum);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a[3][2]={0,1,2,3,4,5};
//    int h=0,l=0;
//    int i=0,j=0;int max=0;max=a[0][0];
//    for(i=0;i<3;i++){
//        for(j=0;j<2;j++){
//            if(a[i][j]>max){
//                max=a[i][j];
//                h=i;
//                l=j;
//            }
//        }
//    }
//    printf("%d %d %d",max,h,l);
//    return 0;
//}
//#include<stdio.h>
//int f(int n){
//    if(n==1||n==2){
//        return n;
//    }
//    else if(n>2){
//        return n*f(n-1);
//    }
//    else{
//        return 0;
//    }
//}
//int main(){
//    int sum=0,n=0,i=0;
//    scanf("%d",&n);
//    for(i=1;i<=n;i++){
//        printf("%d ",f(i));
//    sum+=f(i);
//    }
//    printf("\n");
//    printf("%d\n",sum);
//    return 0;
//}
//#include<stdio.h>
//int main(){
//    int a[20]={0};
//    int max1=0,max2=0;
//    int i=0;
//    for(i=0;i<20;i++){
//        scanf("%d",&a[i]);
//    }
//    max1=max2=a[0];
//    for(i=0;i<20;i++){
//        if(a[i]>max1){
//            max1=a[i];
//        }
//    }
//    for(i=0;i<20;i++){
//    if((a[i]>max2)&&(a[i]!=max1)){
//        max2=a[i];
//    }}
//    printf("%d %d",max1,max2);
//    return 0;
//}
//#include<stdio.h>
//double fun(int n){
//    int i=0;
//    double sum=0;
//    for(i=2;i<=n;i++){
//        if(i%5==0||i%9==0){
//            sum+=1.0/i;
//        }
//    }
//    return sum;
//}
//int main(){
//    int n=0;
//    scanf("%d",&n);
//    double s=0;
//    s=fun(n);
//    printf("%lf",s);
//    return
//#include<stdio.h>
//int main(){
//    int a[3]={3*0};
//    int i=0;
//    for(i=0;i<3;i++)
//        scanf("%d",&a[i]);
//    for(i=1;i<3;i++)
//        a[0]=a[0]+a[i];
//    printf("%d",a[0]);
//    return 0;
//}
#include<stdio.h>
#include <string.h>
#include <assert.h>
void left_move(char*arr,int len,int k){
    int i=0;
    assert(arr!=NULL);//不为空指针，非0，
    for(i=0;i<k;i++){
        int j=0;
        char temp=*arr;//第一步，先挪走第一位，倘若第一步和第二步不分开（都放到循环中），会导致左旋的字符发生变化
        for(j=0;j<len-1;j++){ //如果是右旋的话就是--，len-1是因为少一位(毕竟是从0开始算的)
            *(arr+j)=*(arr+j+1);//第二步，把剩下的往前挪
        }
        *(arr+len-1)=temp;//三步分开，第三步，把第一位放到最后一位，倘若第二步和第三步不分开，会导致最后一位被多次赋值
                            //例如ABCDEF时，会将A赋值到最后一位F，导致F丢失
    }
}
int main(){
    char arr[]={"abcdef"};
    int len=(int)strlen(arr);//注意这里需要转换
    int k=2;
    left_move(arr,len,k);
    printf("%s",arr);
    return 0;
}